CF652F Ants on a Circle

题意：在一个长度为 的圆环上有 只初始位置互不相同的蚂蚁，每只蚂蚁的速度都为 ，初始方向为顺时针或逆时针。

两只运动方向不同的蚂蚁相遇时会调转方向（相遇位置不一定是整数），问 时间后每只蚂蚁的位置。

，，时限 。

---

我们假设蚂蚁在碰撞时穿过对方，那么就能得到最终哪些位置上有蚂蚁。

显然，所有蚂蚁标号的相对顺序是不变的，现在只需再确定某个蚂蚁的标号，或者某个标号的排名。

可以考虑过程中有多少个蚂蚁穿过了位置 ，若顺时针穿过一次，可以看做左侧插入一只蚂蚁，若逆时针穿过，可以看做左侧消失一只蚂蚁。

（这个做法的妙处是，事件“某只蚂蚁穿过”不需要确知其编号）

若某只蚂蚁顺时针移动，且初始位置为 ，则穿过 的次数为 。

若某只蚂蚁逆时针移动，且初始位置为 ，则穿过 的次数为 。

由此不难得到最左侧蚂蚁的编号。

复杂度 。