#5711. 「NordicOI 2026」Catching Apples

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 NordicOI 2026 T4「Catching Apples」

苹果园可以看作是一条一维直线。共有 $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

输入

4
1 1
3 2
5 3
8 1

输出

1
1 1 1 1

在第一个样例中，一个机器人可以按顺序接住每个苹果。

样例 2

输入

3
1 1
2 5
3 1

输出

2
1 2 1

在第二个样例中，苹果 $1$ 和苹果 $3$ 可以由同一个机器人接住，但苹果 $2$ 必须由另一个机器人接住。

样例 3

输入

4
2 2
3 1
3 3
4 2

输出

2
1 1 2 1

在第三个样例中，所需的最少机器人数量为 $2$，但存在多种不同的最优分配方案。

数据范围与提示

详细子任务附加限制及分值如下表所示：