UOJ Logo Universal Online Judge

UOJ

#631. 【UR #21】士兵调度

统计

为了恢复跳蚤国,跳蚤国王需要一支强大的军队,但他现在只是一个光杆司令。于是他来到了国富民强的蛐蛐国,希望能得到蛐蛐国王的支援。跳蚤国王向蛐蛐国王说明了来意。蛐蛐国王稍作思考,表示:“我们可以提供援军,但是需要先经过我的一个考验。”

蛐蛐国王的手下的禁卫军有 $\mathrm{limitn}$ 名士兵,士兵们在一个 $(10^9+1)\times (10^9+1)$ 的巨大网格上的格点处。每个格点的坐标可用数对 $(x,y)$ 表示,其中 $0 \le x \le 10^9$, $0 \le y \le 10^9$。任意时刻不能有两名士兵处在同一个位置。

对于一名士兵,如果与他所在位置 x 坐标相同的人数严格多于与他所在位置 y 坐标相同的人数,那么他就被编入第一组,否则被编入第二组。

一个调度过程是这样的。一开始你可以任意指定这 $\mathrm{limitn}$ 名士兵的位置,只要保证这些位置互不相同且在网格中。这时候每名士兵自动会被分入其中某一组。现在你可以指挥这些士兵进行至多 $\mathrm{limitm}$ 次移动,每次移动可以是将 x 坐标为 $a$ 的所有士兵的 x 坐标改为 $b$,或是将 y 坐标为 $a$ 的所有士兵 y 坐标改为 $b$。但每次移动后仍然要保证不能有两名士兵处在同一位置,且所有士兵位置仍在网格中。

显然,在每次移动后,有一部分(可能一个也没有)士兵所在的分组会改变。假设调度过程中共有 $m\leq \mathrm{limitm}$ 次移动,令第 $i$ 次移动后改变了分组的士兵个数为 $a_i$,则一个移动方式的总评价为 $S=\sum\limits_{i=1}^{m} a_i$。蛐蛐国王认为在调度过程中,最终得到的评价值 $S$ 越大说明指挥官能力越强。

现在蛐蛐国王的考验是:跳蚤国王需要证明他的指挥能力不比蛐蛐国王手下的将官差。于是他需要给出一个调度过程,使得最终得到的评价值 $S\geq \mathrm{minS}$,其中 $\mathrm{minS}$ 是蛐蛐国王手下给出的调度过程所得到的评价值。

跳蚤国王非常愤怒,觉得这个考验是在侮辱他的能力。但由于现在他是光杆司令,需要蛐蛐国的援助,因此他让作为计算机高手的你——伏特来帮他完成考验。

你设计的调度过程可以不用到全部 $\mathrm{limitn}$ 名士兵,即,你可以设定一个 $n\leq \mathrm{limitn}$ 作为士兵数量。

输入格式

一行三个正整数 $\mathrm{limitn},\mathrm{limitm}, \mathrm{minS}$,表示最大士兵数,最大移动次数和你要达到的最低评价值。

输出格式

第一行一个非负整数 $0\leq n\leq \mathrm{limitn}$ 表示你设计的调度过程中的士兵数。

接下来 $n$ 行,第 $i$ 行两个非负整数 $x_i,y_i$ 表示初始时第 $i$ 个士兵在 $(x_i,y_i)$ 位置,需要满足 $0 \leq x_i,y_i \leq 10^9$ 且 $(x_i,y_i)$ 互不相同。

接下来一行一个非负整数 $0\leq m\leq \mathrm{limitm}$ 表示你设计的调度过程中的移动次数。

接下来 $m$ 行每行三个非负整数 $\mathrm{type},a,b$,需要满足 $\mathrm{type} \in \{0,1\},0 \leq a,b \leq 10^9$,其中 $\mathrm{type}=0$ 表示将 x 坐标为 $a$ 的所有士兵 x 坐标改为 $b$,$\mathrm{type}=1$ 表示将 y 坐标为 $a$ 的所有士兵 y 坐标改为 $b$,注意每次移动后不能有两名士兵处在同一位置。

样例一

input

4 3 4

output

4
0 0
1 1
2 2
3 3
3
0 0 1
1 2 1
1 0 3

explanation

这组样例 $\mathrm{limitn}=4,\mathrm{limitm}=3,\mathrm{minS}=4$,你选择了 $n=\mathrm{limitn}=4,m=\mathrm{limitm}=3$。

初始时,$4$ 名士兵分别在 $(0,0),(1,1),(2,2),(3,3)$ 位置,分组为 $(2,2,2,2)$。

第一次移动后,第 $1$ 名士兵移动到了 $(1,0)$,前两名士兵分组改变,现在分组为 $(1,1,2,2)$。

第二次移动后,第 $3$ 名士兵移动到了 $(2,1)$,第 $2$ 名士兵分组改变,现在分组为 $(1,2,2,2)$。

第三次移动后,第 $1$ 名士兵移动到了 $(1,3)$,第 $1$ 名士兵分组改变,现在分组为 $(2,2,2,2)$。

共改变 $S=2+1+1=4$ 次,满足 $S\geq \mathrm{minS}$,因此这是一个合法的调度过程。

注意这并不是在 $\mathrm{limitn}=4, \mathrm{limitm}=3$ 下 $S$ 最大的方案。

样例二

见附加文件中 ex_dispatch2.in,这组样例限制与子任务 $1$ 相同,输出不下发但依然可以提交测试。

数据范围

本题是一道传统题,你需要提交一个输出方案的程序。

本题共有 $4$ 个子任务,每个子任务有且仅有一个测试点,且 $\mathrm{limitn},\mathrm{limitm},\mathrm{minS}$ 均按下表给定。对于一个子任务,只有你的输出合法,并且满足 $S\geq \mathrm{minS}$,你才能获得该子任务的分数。

子任务编号 $\mathrm{limitn}=$ $\mathrm{limitm}=$ $\mathrm{minS}=$ 分值
$1$ $10^3$ $10^3$ $10^3$ $40$
$2$ $10^5$ $300$ $94500$ $20$
$3$ $5\times 10^4$ $13600000$ $20$
$4$ $10^5$ $21100000$ $20$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

校验器

为了方便选手测试,附加文件中我们给出了名为 checker.cpp 的文件,选手可以编译该程序,并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致,且它的效率可能不足够高。你也不需要关心其代码的具体内容。

编译命令为:g++ -std=c++11 checker.cpp −o checker。此外,附加文件中有还有名为 testlib.h 的文件,在编译时,请确保该文件与 checker.cpp 在同一子目录下。

在终端中,checker 的使用方式为:checker <输入文件名> <输出文件名> <输出文件名>。如果你的输入文件名为 dispatch.in,输出文件名为 dispatch.out,则正确的使用方式为 checker dispatch.in dispatch.out dispatch.out

若你的方案正确,校验器会给出 ok 并输出你的调度过程的评价值,否则,该校验器会给出简要的错误信息。

下载

附加文件下载