#P3141. [Hnoi2013]旅行
[Hnoi2013]旅行
[HNOI2013] 旅行
题目描述
在遥远的 HX 国,旅行家小 L 想骑自行车游遍编号为 到 的城市。每座城市或者有一个他想去的景点,或者没有这样的景点。小 L 用程序规划了一条经过所有这些景点的最短路线。按路线,他依次到达城市 ,在 结束旅行。城市的访问顺序已经确定。
到达一座有景点的城市时,小 L 会先游览景点,获得 点快乐值。到达一座没有景点的城市时,他会获得 点疲劳值。他希望恰好用 个月走完全程。每个月可以到达任意多座城市,但至少要到达一座新城市。他在每个月所到达的最后一座城市休息。
用 表示第 个月休息的城市编号,于是 。例如,若 、、路线是 ,计划 意味着第一个月游历城市 ,第二个月游历城市 ,第三个月游历城市 。
对一份计划,令 为第 个月获得的快乐值和疲劳值之差的绝对值。小 L 希望 尽量小。如果有多份计划达到最小值,输出城市编号序列 字典序最小的一份。两个序列从第一个不同的元素开始比较,那个元素较小的序列字典序较小。
输入格式
第一行包含两个正整数 ,分别表示城市数和旅行月数。
接下来 行,第 行包含两个整数 。 是按路线第 个到达的城市编号。 表示该城市有小 L 想去的景点, 表示没有。 是 的一个排列。
输出格式
输出一行 个用空格分隔的整数 ,表示最优计划中每个月休息时所在的城市编号。
样例
8 3
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0
1 6 8
按样例输出,第一个月各获得 点快乐值和疲劳值,后两个月每月各获得 点快乐值和疲劳值。因此最大差值为 。达到这个值的序列是 、 和 ,其中 的字典序最小。
数据范围
本题数据满足 、。原题叙述给出 ,本题数据含 ,此时每个月恰好到达一座新城市。