故事
某公司目前的目标是创造一个舒适的工作环境。公司决定从今年四月新员工加入公司开始,每周对办公室进行一次清洁工作。 然而,分配清洁职责并不容易。有各种限制,例如,职责不应该集中在一个人身上,对于尚未习惯工作的新员工来说,负担应该特别低。 此外,分配的任务应该易于记忆,例如“在员工 X 之后,下一个必须是员工 Y 或 Z”。 创建尽可能遵循约束的清洁计划。
问题陈述
有 N 某公司员工,编号为 0 to N-1。 对于每位员工 i (0 \leq i \leq N-1),您必须确定两个整数 a_i 和 b_i (a_i 和 b_i 可能相等)。 然后,每周的清洁计划通过以下方式创建:
- 第一周,员工 0 将进行清洁工作。
- 从第二周开始,让员工 x 是上周打扫卫生的人,让 t 是员工工作的周数 x 已于上周末被指派为清洁工。那么,本周的保洁值班确定如下:
- 当 t 为奇数:员工 a_x
- 当 t 是偶数:员工 b_x
对于每个 i (0 \leq i \leq N-1),目标次数 T_i 给出为员工的次数 i 应在接下来的时间分配清洁任务 L = 500\,000 周。 让 t_i 为员工实际出勤次数 i 被分配清洁任务。 创建一个清洁计划,使错误定义为 \left|t_0 - T_0\right| + \left|t_1 - T_1\right| + \cdots + \left|t_{N-1} - T_{N-1}\right| 尽可能小。
评分
让 E 是输出清洁计划中的错误。您将获得的分数 10^6 - E,保证为非负数。
有150个测试用例,提交的分数是每个测试用例的总分。如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE,提交的分数将为零。比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。
输入
输入由标准输入按以下格式给出:
N L
T_0 T_1 \cdots T_{N-1}
- 员工人数 N 固定为 100 跨所有测试用例。
- 周数 L 固定为 500\,000 跨所有测试用例。
- 0 \leq T_i \leq 10\,000.
- T_0 + T_1 + \cdots + T_{N-1} = L.
- 给定值均为整数。
输出
按以下格式输出到标准输出:
a_0 b_0
a_1 b_1
\vdots
a_{N-1} b_{N-1}
这里,如果存在 i (0 \leq i \leq N-1) 不满足 0 \leq a_i \leq N-1 or 0 \leq b_i \leq N-1,输出将被判断为 WA.
输入生成
让 \mathrm{rand}(L, U) 是生成均匀随机整数的函数 L 和 U,包括在内。输入将按照以下算法生成:
- 对于每个 i (0 \leq i \leq N-2),生成 T_i 与 \mathrm{rand}(0, 10000).
- 如果总和 S = T_0 + \cdots + T_{N-2} 满足 0 \leq L - S \leq 10000,设置 T_{N-1} = L - S 并完成输入。否则,请重试步骤 1。
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。