#P1384. [Baltic2000]Time Zones
[Baltic2000]Time Zones
题目描述
给定一个整数 ,现在将世界划分为 个时区,分别编号为第 时区到第 时区,您在第 时区。
在第 时区的一天之内,恰好收到每个时区各发来的一条消息(包括第 时区)。消息瞬时传输,按接收时刻严格递增的次序给出,没有两条消息同时到达;消息中仅保留发送地的当地时刻 。
保证 ,。
时区自第 时区向西编号。从第 时区当地时间换算为第 时区时间,需要加 小时;本题不跨日期,换算后的小时数仍应在 内。
求这 个时间信息分别来自哪几个时区。保证给定数据存在唯一的合法答案。
输入格式
第一行一个整数 代表时区数和时间消息数。
接下来 行每行一个四位数字串 hhmm,代表一个时间消息;小时和分钟均补足两位。
比如 , 最终表示结果就是 。
输出格式
一行 个整数代表每个时间消息来自哪个时区。
5
0017
0250
0400
0201
0002
3 1 0 2 4
样例说明
注意样例 的第 个数据,该时间消息必须来自第 时区,因为其他时区的时间消息到第 时区都要至少经过 小时, 最小值为 ,就超过了 的范围。
数据规模与约定
对于 的数据,,,。
本站修复版的结构保证
原官方题面给出的唯一答案保证仍保留。本站修复版另明示下面更强的、可独立检查的结构条件;它来自对全部原输入的核验,不冒称官方原文已有此条件,也不认为任意唯一解实例都满足它。
对每条消息i,建立其允许时区候选集合,初始为0到n-1-h_i。反复执行以下两类必要性删除,直到候选集合不再变化:
- 相邻消息支持过滤:若不存在某个相邻消息的候选时区,使两条消息的时区不同且换算接收时间保持严格递增,就删除当前候选。两个方向均检查。
- 全异匹配支持过滤:在“消息到候选时区”的二分图中,删除不属于任何完美匹配的候选边。
保证在这个不动点处,每条消息的候选集合都只剩一个时区。该条件不依赖所选完美匹配或必要性删除的处理顺序。它允许使用候选传播、完美匹配与交替图强连通分量的多项式算法,不需要把60个时区的阶乘搜索当作可控。
本站11份原输入均已完整校验,分别在1到6轮传播后满足该条件。上述条件定义整个可接受输入类别,并非按文件哈希挑选答案或按某台机器的运行时长限定输入。