自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:12:50，当前版本为作者最后更新于2025-04-24 14:59:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很怀疑出题人的精神状态。首先注意到题目一共给出了给点排序的 $m$ 条限制，而只需要满足 $\lceil\frac{m}{2}\rceil$ 个要求即可。这说明如果我们构造出了一个不符合要求的方案，那么取其补方案（在本题中就是将排序反向，注意补方案会使得原本满足的限制不满足，反之亦然）就一定是符合要求的。所以只需要随便取一个排列判定是否合法，如果不合法就倒过来输出即可。时间复杂度 $O(\sum n+m)$，QOJ Submission。