Pairing Pairs 已加强

yummy · 2024-03-12 21:52:40 · 个人记录

n\le 10^7 版本，欢迎测试。

该版本和赛时代码有较大区别，请注意区分。

交互库的实现

正式版本的交互库流程如下：

读入 Seed,n,m（特别地，Seed 是十六进制），其中 Seed\bmod 16 决定了这个测试点数据的类型。

接下来分类讨论：

• 如果 Seed=0，则该测试点手动读入。
• 如果 Seed\bmod 16=0，则该测试点为菊花图。
• 否则分类讨论。目前已经有 1,2,3 三个类型，但是我暂时不告诉你是什么。

总之生成完数据后，yummy 会把 u,v 可能复制一遍然后发给你（是否复制取决于类型）。所以不要指望着通过修改输入骗到分数。

然后交互库会获取你的返回数组。

• 如果该测试点是菊花图，那么交互库会直接验证是否全 -1。
• 否则可以证明无解的边只有常数条，所以交互库会验证你给出的所有答案，然后向 checker 输出所有你认为无解的边。（因此如果全返回 -1，你可能 TLE 而非 WA。）

本题特供的快速 shuffle

std::shuffle 和手写洗牌算法速度都太慢了，然而本题事实上不需要严格地让每一个排列出现的概率均等，因此本题的 p 使用特供的 shuffle 生成：

const int Msk=(1<<17)-1;
for(int i=1;i<n;i++)std::swap(p[i],p[rnd()&Msk]);

其好处有二：

• 避免了取余运算。
• 前 Msk 个数能够塞进 cache，加速了内存访问。

在 yummy 的本机测试上，n=3\times 10^7 时，std::shuffle 用时 765 毫秒，特供 shuffle 用时 69 毫秒。

贡献数据

同时限于 yummy 的想象力，本题的 generator 甚至弱于原题，所以需要大家合力贡献数据以维持数据强度。

目前已经支持的方案有两种，如果你有特殊需求可以联系 yummy：

方案 1：直接输出

适合 n 不太大的情形。格式只需要在 sample_interactive_lib.cpp 输入格式基础上，前面加个 0。

方案 2：在线生成

你只需要给出一个代码片段。你可以使用的东西有：

• rnd()，获得一个 [0,2^{32}-1] 内的整数。
• p[0],p[1],...,p[n-1]，一个比较乱的全排列。

你需要给数组 u,v 赋值。

注意：使用该方法时，请确保你的数据生成器是 O(n) 的，且如果可以，请稍微注意下常数。

下面是 yummy 的菊花图生成代码，供参考：

int cen=p[0];
for(int i=1;i<n;i++)
{
  if(p[i]>cen){
    u[i]=cen;
    v[i]=p[i];
  }
  else{
    u[i]=p[i];
    v[i]=cen;
  }
}
u[0]=u[n-1];
v[0]=v[n-1];
a=find_pairs(n,n-1,u,v);
/*下面是菊花图特有的部分，你只需要写个 break; 即可。
for(int i=0;i<n-1;i++)
  if(a[i]!=-1){printf("%d,",Err);return 0;}
printf("%d,",Fin);
return 0;
*/