P16380 [NordicOI 2026] Catching Apples 接苹果

翻译来源：loj [#5711. 「NordicOI 2026」Catching Apples](https://loj.ac/p/5711)。 3s，1024MB。 Subtask 0 为样例。

苹果园可以看作是一条一维直线。共有 $N$ 个苹果，第 $i$ 个苹果在时间 $t_i$ 掉落在位置 $x_i$。 机器人的最大移动速度为 $1$。为了接住第 $i$ 个苹果，机器人必须在时间 $t_i$ 恰好位于位置 $x_i$。每个机器人可以从任意位置出发，在接住最后一个苹果后，它可以停在任意位置。 你的任务是使用尽可能少的机器人接住所有苹果。你还需要输出每个苹果由哪一个机器人接住。

第一行包含一个整数 $N$ $(1 \leq N \leq 2 \cdot 10^5)$，表示苹果的数量。 接下来 $N$ 行，每行包含两个整数 $t_i$ 和 $x_i$ $(1 \leq t_i, x_i \leq 10^9)$，分别表示第 $i$ 个苹果掉落的时间和位置。 所有 $(t_i, x_i)$ 坐标对都是不同的。

输出一个整数 $K$，表示接住所有苹果所需的最少机器人数量。 接下来一行输出 $N$ 个整数 $a_1, a_2, \dots, a_N$，其中 $a_i$ 表示接住第 $i$ 个苹果的机器人编号。 机器人编号必须在 $1$ 到 $K$ 之间，且 $1$ 到 $K$ 的每个编号都必须至少使用一次。 如果存在多种最优分配方案，你可以输出其中任意一种。 仅对于第 $4$ 组数据，允许只输出整数 $K$。

### 评分 详细子任务附加限制及分值如下表所示： | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $15$ | $N \leq 20$ | | $2$ | $13$ | 最少机器人数量不超过 $2$ | | $3$ | $20$ | $N \leq 5000$ | | $4$ | $27$ | 仅需输出机器人数量 $K$，无需提供分配方案 | | $5$ | $25$ | 无附加限制 | ### 样例解释 在第一个样例中，一个机器人可以按顺序接住每个苹果。 在第二个样例中，苹果 $1$ 和苹果 $3$ 可以由同一个机器人接住，但苹果 $2$ 必须由另一个机器人接住。 在第三个样例中，所需的最少机器人数量为 $2$，但存在多种不同的最优分配方案。