【Codeforces 652F】Ants on a Circle

        最终所有蚂蚁的位置（不管是哪只蚂蚁在哪个位置）是很容易确定下来的，可以看作有所的蚂蚁不管碰撞，一路走到底。

        最终所有蚂蚁的相对位置也是可以确定下来的，因为每次碰撞并不会影响蚂蚁们的相对位置。

        这个问题的难点在于如何判断最后任意一只蚂蚁的位置。

        官方题解里给出了一个比较显然的做法：由于当所有蚂蚁走m次后蚂蚁们的位置集合与初始相同，可以模拟出一只蚂蚁在m的时间里走到了哪个位置，然后其他蚂蚁的位置也就可以确定下来。这样再循环走若干次，最后再走t%m的时间，就能得到所有蚂蚁的最终位置了。

        由于我们只需要知道一只蚂蚁在m的时间里走到了哪里，所以其他蚂蚁的编号我们都先不管。在m的时间里一只蚂蚁最多发生2n次碰撞，所以这个可以开两个堆维护向左、向右走的蚂蚁，每次更新碰撞事件，时间复杂度\(O(nlogn)\)。

        有些时候会发现有两只蚂蚁在我们求出的那个位置上。那么这时再模拟出另一只蚂蚁的最终位置就好了。

        这么写起来稍微会麻烦一点，在评论区里有一个人给出了一个非常简单的做法：

        官方题解里的做法以一只蚂蚁的位置为基础，求出其他蚂蚁的位置。

                  一个更简单的做法是，我们可以通过找最终位置>=0的第一只蚂蚁是哪一只，同样可以求出最终每个位置上的蚂蚁是哪只。

                  假设在某一时刻，位置>=0的蚂蚁是第i只蚂蚁（这里的蚂蚁编号按照排序后的顺序给）。

                  考虑x=0这个点。如果在该时刻之后，有一只蚂蚁从x=m-1走到了x=0，说明有一只蚂蚁排在了第i只蚂蚁的左边，此时位置>=0的蚂蚁是第i-1只蚂蚁；

                  如果在该时刻之后，有一只蚂蚁从x=0走到了x=m-1，说明有一只蚂蚁跑到最右边去了，此时位置>=0的的蚂蚁是第i+1只蚂蚁。

                  非常好的一点是，我们无须关心是哪只蚂蚁从x=0走开了，只需要知道有蚂蚁这么走。

                  于是就可以很轻易地知道最终位置上的位置>=0的第一只蚂蚁是哪只了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=300010;

int p[maxn],dir[maxn],rank[maxn];
int ans[maxn];
int n,m;
long long t;

bool cmp(const int &a,const int &b) {return p[a]<p[b];}

int main()
{
	scanf("%d%d%I64d",&n,&m,&t);
	t%=(long long)n*m;
	for (int i=1;i<=n;i++)
	{
		char ch[4];
		scanf("%d %s",&p[i],ch);
		p[i]--;
		dir[i]=(ch[0]=='L')?-1:1;
		rank[i]=i;
	}
	sort(rank+1,rank+1+n,cmp);
	int s=0;
	for (int i=1;i<=n;i++)
	{
		if (dir[i]==1) s=(s-(p[i]+t)/m)%n;
		else s=(s-(p[i]-t-m+1)/m)%n;
		p[i]=((p[i]+dir[i]*t)%m+m)%m;
	}
	s=(s+n)%n;
	sort(p+1,p+1+n);
	rotate(rank+1,rank+1+s,rank+1+n);
	for (int i=1;i<=n;i++) ans[rank[i]]=p[i]+1;
	for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}