aish @ 2023-07-01 10:16:23
在第 8 个点上一直TLE，自己类似生成数据本地测可以过。
生成如下：
from random import randint as rd
with open("1.in", "w") as f:
n, m, k, t = 200, 200, 1000000, 999900
print(n, m, k, t, file = f)
for i in range(k):
# print(rd(1, n), rd(1, m), rd(-50, 50), file = f)
print(101, 101, rd(-1000000, 1000000), file = f)
这是提交记录：Submission
我不理解为什么。
by aish @ 2023-07-01 11:22:30
实测把
but[lab[x]]改为
but[(x - 1) / BLO]即可。
我不理解预处理为什么会更慢……
by Cap1taL @ 2023-07-13 08:51:38
@aish CF题解说给每个Cell的数排序有助于利用缓存，我sort了之后直接从TLE变1.5s了你可以试试
by aish @ 2023-07-13 08:54:56
@_XHZSXY 意思是把每一个点内的值 sort 一遍吗？
by Cap1taL @ 2023-07-13 08:56:06
@aish 对，对于每个格子sort，原理我也不是很懂
by Cap1taL @ 2023-07-13 08:56:24
而且第八个点不止有101,101的，还有别的
by aish @ 2023-07-13 08:58:35
@_XHZSXY 多谢，我再研究一下
by Cap1taL @ 2023-07-13 09:03:00
@aish 我之前Debug的时候是拿你的gen改了改用的，一下就拍出来错了
from random import randint as rd
with open("1.in", "w") as f:
n, m, k, t = 200, 200, 1000000, 100
print(n, m, k, t, file = f)
for i in range(k//2):
# print(rd(1, n), rd(1, m), rd(-50, 50), file = f)
print(101, 101, i, file = f)
for i in range(k//2):
# print(rd(1, n), rd(1, m), rd(-50, 50), file = f)
print(rd(1,200), rd(1,200), rd(-100,100), file = f)
by aish @ 2023-07-13 09:12:29
@_XHZSXY 我看了一下关于cpu缓存的文章。
程序在读取数据时，会先复制到 L1 缓存之中。
原文：当CPU从内存读数据时，如果该数据没有在缓存中(read miss)，CPU会把数据拷贝到缓存。
来自：https://zhuanlan.zhihu.com/p/80672073?utm_id=0
但是 L1 缓存很小，一般来说在 64kb 左右，也就是可以存 8192 个 int 的样子。所以按照顺序访问内存块数据在缓存中的写入和擦出更少，导致程序更快。可能这也是我用 lab 数组预处理会更慢的原因。因为会导致更多的写入和擦出。
by Cap1taL @ 2023-07-13 09:14:12
@aish 牛啊
by Cap1taL @ 2023-07-13 09:14:29
@aish 我现在是卡在 Test27过不去了，最难过的一集