#P17572. [JAG 2026 Summer Camp #3] Ants Sort
[JAG 2026 Summer Camp #3] Ants Sort
题目描述
有一条线段,其左、右端点分别是位于坐标 和 处的墙壁。规定向右为正方向。
线段上有 只蚂蚁,从左到右编号为 。第 只蚂蚁最初位于坐标 ,因此有 。它携带编号为 的球。当 为 L 时,它最初朝左;当 为 R 时,它最初朝右。
在时刻 ,所有蚂蚁同时开始以每秒 个单位长度的速度,沿各自朝向移动。
当一只蚂蚁撞到墙壁时,它会立即反向。当两只蚂蚁相撞时,它们都会立即反向。此时,你可以选择是否交换它们携带的球。
你的目标是使每个 ()对应的第 只蚂蚁都携带编号为 的球。可以证明,这一目标总能实现。求最早能够实现该目标的时刻。
输入格式
输入包含一组测试数据,格式如下。
N M
X_1 P_1 D_1
X_2 P_2 D_2
...
X_N P_N D_N
第一行包含两个整数 和 (,,且 为偶数),分别表示蚂蚁的数量和右侧墙壁的坐标。
对于每个 (),接下来 行中的第 行包含两个整数 和一个字符 ,分别表示第 只蚂蚁的初始坐标、最初携带的球的编号,以及初始朝向。坐标 均为偶数,满足 。序列 是 的一个排列,且不等于 。每个 均为 L 或 R。
输出格式
输出最早能够实现目标的时刻。保证答案为整数。
3 10
2 3 R
4 1 R
8 2 L
7
2 943168
168 2 L
874 1 R
942815
9 168598874
2 2 L
4 9 R
8 4 L
16 3 L
32 1 R
64 6 R
128 8 R
256 5 R
512 7 L
168598856