[COCI 2021/2022 #5] Fliper

Luogu
IDLGP8326
Time3000ms
Memory512MB
DifficultyP6
2021Special JudgeCOCI(克罗地亚)
现有一个包含 $n$ 块挡板的旧弹球机。 游戏在二维平面内进行,其中每块挡板与坐标轴所夹锐角总为 $45^\circ$,长度为 $1$ 个单位。挡板用其中心坐标 $(x_i,y_i)$ 和字符 / 或 \ 来表示。小球在碰到挡板后,其运动方向将会旋转 $90^\circ$。注意,挡板的两面都可使小球的运动方向发生偏转。 不难发现,当小球处于弹球机中时,它只有两种结局: - 沿着某一方向一直运动下去而不碰到挡板 - 处于若干个挡板的循环之中 在翻新弹球机的过程中,有四种颜色的染料可供选择。现要将弹球机中的每个挡板进行染色,使得**每一个**循环内经过每一种颜色的次数相同且为偶数。 请给出一种符合题意的染色方式,或证明这样的染色方式不存在。如果不存在,输出 `-1`。 ## Input 第一行一个正整数 $n$,表示挡板的数量。 接下来的 $n$ 行,每行两个正整数 $x_i,y_i$ 和一个字符 $c_i$(/ 或 \),表示一个挡板。数据保证,挡板的位置不会相互重合。 ## Output 如果不存在符合题意的染色方式,输出 `-1`。 否则输出 $n$ 个整数 $1 \sim 4$,表示 $n$ 个挡板所选择的染料颜色。如果有多种符合题意的方式,输出任意一种。 [samples] ## Note **【样例 2 图解】** ![](https://cdn.luogu.com.cn/upload/image_hosting/ksajf2n4.png) **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1(20 pts):$1 \le n \le 40$。 - Subtask 2(20 pts):最多存在一个循环。 - Subtask 3(70 pts):无特殊限制。 对于 $100\%$ 的数据,$1 \le n \le 5 \times 10^5$,$0 \le |x_i|,|y_i| \le 10^9$。 **【说明】** 本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/g6cdziry)。如果对此有疑问或想要 hack,请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或[发帖](https://www.luogu.com.cn/discuss/lists?forumname=P8326)。 **【来源】[COCI 2021-2022#5](https://hsin.hr/coci/archive/2021_2022/contest5_tasks.pdf) Task 3 Fliper。**
Samples
Input #1
4
1 1 \
3 1 /
3 2 \
1 2 /
Output #1
-1
Input #2
9
1 2 \
1 3 /
2 1 \
2 2 \
2 3 \
3 1 /
3 2 \
4 2 /
4 3 \
Output #2
1 3 2 4 1 3 2 4 1
Input #3
12
1 2 \
1 3 /
2 1 \
2 2 \
2 3 \
2 4 /
3 1 /
3 2 \
3 3 \
3 4 \
4 2 /
4 3 \
Output #3
1 3 2 4 2 4 1 3 1 3 2 4
API Response (JSON)
{
  "problem": {
    "name": "[COCI 2021/2022 #5] Fliper",
    "description": {
      "content": "现有一个包含 $n$ 块挡板的旧弹球机。 游戏在二维平面内进行,其中每块挡板与坐标轴所夹锐角总为 $45^\\circ$,长度为 $1$ 个单位。挡板用其中心坐标 $(x_i,y_i)$ 和字符 / 或 \\ 来表示。小球在碰到挡板后,其运动方向将会旋转 $90^\\circ$。注意,挡板的两面都可使小球的运动方向发生偏转。 不难发现,当小球处于弹球机中时,它只有两种结局: - 沿着某一方向一直运",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8326"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "现有一个包含 $n$ 块挡板的旧弹球机。\n\n游戏在二维平面内进行,其中每块挡板与坐标轴所夹锐角总为 $45^\\circ$,长度为 $1$ 个单位。挡板用其中心坐标 $(x_i,y_i)$ 和字符 / 或 \\ 来表示。小球在碰到挡板后,其运动方向将会旋转 $90^\\circ$。注意,挡板的两面都可使小球的运动方向发生偏转。\n\n不难发现,当小球处于弹球机中时,它只有两种结局:\n\n- 沿着某一方向一直运...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments