logo AlgoBeat OnlineJudge
登录 注册

#215304. [NWERC 2025] Juggling Keys

内存限制:2048 MiB 时间限制:5000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

接近一百人参与使 NWERC 成为可能——组织者、志愿者、评委、系统和流媒体团队,以及最后但同样重要的 DOMjudge 团队,他们负责评判系统。他们每年都参加 NWERC,并且在那里总是玩得很开心!

DOMjudge 团队成员喜欢在 NWERC 期间合租一套公寓,但通常没有足够的钥匙供每人一把。这可能会让后勤变得有些棘手:有些人喜欢早早出门吃早餐,其他人则在圣诞市场待到很晚,还有一些人可能回公寓快速午睡。如果有人返回公寓时另一个人已经在公寓里,他们可以按门铃,然后会被放进去。然而,如果有人返回时公寓是空的,他们就需要随身带一把钥匙。

给定每个人外出旅行的时间,确定每个人何时应该随身带一把钥匙,以便每个人都能进入公寓而不会被(暂时)锁在门外。

图 J.1:样例输入 的示意图,有 个 DOMjudge 团队成员, 把钥匙,总共 次旅行。携带钥匙的旅行用粗体显示。有两次,一个人回到空房子,必须使用自己的钥匙开门。

输入格式

输入包括:

  • 一行三个整数 ),表示 DOMjudge 团队成员的数量、钥匙的数量和旅行的数量。
  • 行,每行三个整数 ),描述一次旅行,其中人员 在时间 离开,在时间 返回。

任何时候,最多只有一个人到达或离开。

保证对于每个人,他们的旅行不会接触或重叠。

输出格式

如果可能分配钥匙使得没有人被锁在门外,输出一个长度为 的字符串,其中每个字符是 01 。如果进行第 次旅行(按输入顺序)的人应该随身带一把钥匙,则字符串的第 个字符是 1 。否则,输出 0。 如果有多个有效解决方案,你可以输出其中任意一个。

样例

样例输入 1

3 2 5
3 0 9
1 2 18
2 4 7
3 12 22
2 14 20

样例输出 1

01110

样例输入 2

2 1 2
1 2 4
2 1 3

样例输出 2

01

样例输入 3

2 1 3
1 1 5
2 2 3
2 4 6

样例输出 3

impossible