#PQJ2294x13453. QOJ 2294_13453

    ID: 2788 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训

QOJ 2294_13453

标题: 大鱼划水 - Problem - QOJ.ac

#13453. 大鱼划水

Statistics

The problem was used in the following contests:

你是大鱼,一天你在海里划水。

海可以看成一个坐标平面,海上有 n 座小岛,第 i 座小岛的坐标为 (xi,yi),上面居住着 i 个人。

你喜欢沿着平行于 x 轴或 y 轴的方向进行划水,你觉得一条划水的路线是快乐的,如果它满足如下条件:

  1. 该路线平行于 x 轴,从纵坐标负无穷远处划到正无穷远处;或该路线平行于 y 轴,从横坐标负无穷远处到正无穷远处。
  2. 沿着你划水的方向,至少经过一座小岛。
  3. 你会求出沿途经过的所有小岛的人数的最大公约数,这个数最终为 1。

(ps: 特别地,定义一个数的最大公约数就是它本身)

你希望有尽可能多的快乐的划水路线,于是你找到了水神,希望她帮你控制这片海域来完成你的目标。

不幸的是,水神不能改变这些小岛的坐标,她只能调整每座小岛的人数,且需要保持 n 座小岛的人数恰为 1∼n 的一个排列。

不过水神的计算能力不怎么好,因此她需要你给出一组方案,然后她会按照你的方案来重新分配这 n 座小岛的人数。

因此你的任务是:找出一组调整小岛人数的方案,使得在满足水神的条件下,快乐的划水路线数尽可能多。

输入格式

本题包含多组数据。

第一行包含一个正整数 T,表示数据组数。

对于每组数据,第一行包含一个正整数 n,表示小岛的个数。

接下来 n 行,每行两个正整数 xi,yi,表示一座小岛的坐标。保证所有小岛的坐标两两不同。

输出格式

对于每组数据,输出两行:

第一行输出一个整数,表快乐的划水路线的数量的最大可能值。

第二行输出 n 个整数,表示每座小岛的人数,按照输入的顺序输出。你需要保证你输出的 n 个数恰为 1∼n 的排列。

如果有多组解,输出任意一组均可。

注意:如果你对于所有的数据,第一行的输出均正确,可以获得该子任务 25% 的分数。但是如果你只要这个部分分,你也要在第二行输出一个排列 (但不需要满足你的答案)。

样例数据

样例 1 输入

2
4
1 1
1 2
2 1
2 2
5
1 1
2 2
4 4
8 8
16 16

样例 1 输出

4
1 2 4 3
2
1 2 3 4 5

样例 1 解释

对于第一组数据:

快乐的划水路线有四条:x=1 (沿途经过的小岛人数分别为 1,2)、x=2 (人数分别为 4,3)、y=1 (人数分别为 1,4)、y=2 (人数分别为 2,3)。

对于第二组数据:

快乐的划水路线有两条:x=1 (人数分别为 1)、y=1 (人数分别为 1)。

样例 2

见下发文件

子任务

对于所有的测试点,均满足 1≤T,n≤2×105;∑n≤2×105;1≤xi,yi≤109,对于 i≠j,保证 xi≠xj∨yi≠yj。

具体的子任务的数据规模见下表:

子任务 分值 n T xi,yi 其他性质 1 4 ≤9 ≤6 ≤n 无 2 4 ≤2×105 ≤2×105 ≤109 xi=yi 3 4 ≤2×105 ≤2×105 ≤109 yi=1 4 4 ≤2×105 ≤2×105 ≤109 yi≤2 5 8 ≤9 ≤2×105 ≤n 无 6 8 ≤50 ≤50 ≤109 ∑n≤2500 7 8 ≤2500 ≤2500 ≤109 ∑n≤2500 8 8 ≤2×105 =1 ≤109 保证所有小岛构成一个 4−连通块 9 4 ≤2×105 ≤2×105 ≤109 保证所有小岛构成一个 4−连通块 10 8 ≤2×105 =1 ≤109 保证每条平行于坐标轴的直线经过的小岛个数不等于 2 11 4 ≤2×105 ≤2×105 ≤109 保证每条平行于坐标轴的直线经过的小岛个数不等于 2 12 8 ≤2×105 =1 ≤109 保证每条平行于坐标轴的直线经过的小岛个数等于 0 或 2 13 4 ≤2×105 ≤2×105 ≤109 保证每条平行于坐标轴的直线经过的小岛个数等于 0 或 2 14 8 ≤2×105 =1 ≤10000 保证所有小岛的坐标在可行域内均匀随机 15 4 ≤2×105 ≤2×105 ≤10000 保证所有小岛的坐标在可行域内均匀随机 16 8 ≤2×105 =1 ≤109 无 17 4 ≤2×105 ≤2×105 ≤109 无

注:两个整点 A,B 是 4−连通的,当且仅当存在一个整点序列 P0=A,P1,P2,⋯,Pm−1,Pm=B,使得 |PiPi+1|=1 (0≤i<m)。

注意:如果你对于所有的数据,第一行的输出均正确,可以获得该子任务 25% 的分数。但是如果你只要这个部分分,你也要在第二行输出一个排列 (但不需要满足你的答案)。(很重要所以说两遍)

此外,为了选手的身心健康,我们在下发文件中准备了一份 checker.cpp,请大家自行编译使用,使用方法及头文件参见 testlib 标准。