CF429E Points and Segments

Iahub 不擅长解几何题，但他听说今年 IOI 选拔营会有很多几何题。为此，Iahub 被吓得把自己锁在地下室，开始思考新的几何类题目。其中之一如下： Iahub 想在 $OX$ 轴上画 $n$ 个互不相同的线段 $[l_i, r_i]$。每条线段可以涂成红色或蓝色。如果满足以下条件，则称这个画法是好的：对于 $OX$ 轴上的每一个点 $x$，设所有包含点 $x$ 的线段中，有 $r_x$ 条是红色，$b_x$ 条是蓝色；则每一个点 $x$ 都必须满足 $|r_x - b_x| \leq 1$。 一条线段 $[l, r]$ 包含点 $x$ 当且仅当 $l \leq x \leq r$。 Iahub 给你所有线段的起点和终点。你需要为他找出一种好的染色方案。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示线段的数量。接下来的 $n$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \leq l_i \leq r_i \leq 10^9$），表示第 $i$ 个线段的起点和终点。 保证所有线段互不相同。

如果不存在满足要求的方案，输出一个整数 $-1$。否则输出 $n$ 个整数，每个整数为 $0$ 或 $1$，第 $i$ 个数表示第 $i$ 条线段的颜色（$0$ 表示红色，$1$ 表示蓝色）。 如果有多种方案，输出任意一种均可。

由 ChatGPT 5 翻译