想当然的以为Linux下换行符没有\r,所以没有判,5发 0% INCORRECT,正式退赛了
。
昨晚熬夜把19630345的数据优化到了6.3s,分享一下我个人的经验。
1. 存图用vector会很慢。考虑把所有边排个序,那么一个点的所有出边就是一段连续的区间,再遍历就会快很多了。
2. 给边排序是很花时间的,但考虑到离散化本身就需要排序(写的不精细的hash其实不会比排序快),所以可以把给边排序和离散化同时完成。可以参考下面的代码:
// 边的定义
struct Edge {
uint32_t x, y, z;
};
void SortEdges() {
RadixSortY();
uint32_t last = E[0].y - 1;
for (int i = 0; i < edge_cnt; ++i) {
if (E[i].y != last) {
table[n++] = E[i].y;
last = E[i].y;
}
E[i].y = n - 1;
}
RadixSortX();
memset(st, -1, sizeof(st));
memset(ed, -2, sizeof(ed));
int ptr = 0;
for (int i = 0; i < edge_cnt; ++i) {
if (E[i].z == 0) break;
while (ptr < n && table[ptr] < E[i].x) ptr += 1;
if (ptr < n && table[ptr] == E[i].x) {
E[i].x = ptr;
if (st[ptr] == -1) st[ptr] = i;
ed[ptr] = i;
} else {
E[i] = {~0U, ~0U, 0};
}
}
}
其中 RadixSortY() 是以 y 为关键字,对所有边进行基数排序,注意基数排序按256分组会快;RadixSortX() 是以 x 为关键字,对所有边进行基数排序。table[] 表示离散化后的值在离散化之前是什么;st[i] 和 ed[i] 表示以 i 为起点的所有出边在边集里所在的位置(一个区间)。
3. 上述过程中边都是 struct {x, y, z}; 这样存的,但后面遍历的时候其实 x 已经没用了,所以排完序之后可以重新定义一个 struct {y, z};,再遍历可以快得多。
4. 计算的时候IO资源没有充分利用,可以考虑把计算中的一部分分离出来。我的做法是(感谢chier提供这个思路):搜索时,答案先存到一个 uint32_t 的数组里,而不是直接存成字符串。等搜完之后再把 uint32_t 的答案转成 char,在这个转换过程中可以同时开一个线程负责输出。这样就可以实现流水线,快很多。
还有很多技巧,但应该都是well-known的,就不多提了。过几天会抽时间把代码整理一下放到GitHub。
感谢这个比赛给我机会可以认识这么多人。祝进决赛的大佬们奖金多多!


Orz ddd
膜拜大佬,同0% INCORRECT,不过还是大佬强,我1963W得10s。本来挺失落的,看了大佬,发现原来我不是最惨的。
膜拜
膜拜
膜
前排膜拜