#PQJ2294x13453. QOJ 2294_13453
QOJ 2294_13453
标题: 大鱼划水 - Problem - QOJ.ac
#13453. 大鱼划水
The problem was used in the following contests:
你是大鱼,一天你在海里划水。
海可以看成一个坐标平面,海上有 n 座小岛,第 i 座小岛的坐标为 (xi,yi),上面居住着 i 个人。
你喜欢沿着平行于 x 轴或 y 轴的方向进行划水,你觉得一条划水的路线是快乐的,如果它满足如下条件:
- 该路线平行于 x 轴,从纵坐标负无穷远处划到正无穷远处;或该路线平行于 y 轴,从横坐标负无穷远处到正无穷远处。
- 沿着你划水的方向,至少经过一座小岛。
- 你会求出沿途经过的所有小岛的人数的最大公约数,这个数最终为 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 标准。