感觉这个思路好巧妙啊。
我们能发现不管怎么碰撞,初始态和最终态蚂蚁间的相对顺序都是一样的, 并且所占的格子也是一样的, 那么我们就只需要
找到其中一个蚂蚁的最终位置就能确定所有蚂蚁的位置了, 我们考虑找初始为止离0最近的那个蚂蚁的最终位置,我们能发现
蚂蚁从m-1->0 rk++, 蚂蚁从0->m-1 rk–, 在取模意义下rk就是那个蚂蚁的最终位置。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long longusing namespace std;const int N = 1e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-);LL n, m, t, cnt, X[N], ans[N];
char T[];struct node {
LL s, d, id;
bool operator < (const node& rhs) const {
return s < rhs.s;
}
} a[N];int main() {
scanf("%lld%lld%lld", &n, &m, &t);
for(int i = ; i < n; i++) {
scanf("%lld%s", &a[i].s, T);
a[i].s--; a[i].id = i;
if(T[] == 'L') a[i].d = -;
else a[i].d = ;
}
sort(a, a + n);
for(int i = ; i < n; i++) {
if(a[i].d == ) {
X[i] = (a[i].s + t) % m;
cnt = (cnt + (a[i].s + t) / m) % n;
} else {
X[i] = (a[i].s - t) % m;
cnt = (cnt + (a[i].s - t) / m) % n;
if(X[i] < ) X[i] += m, cnt = (cnt - ) % n;
}
}
sort(X, X + n);
cnt = (cnt % n + n) % n;
int now = ;
for(int i = cnt; i < n; i++) ans[a[now++].id] = X[i] + ;
for(int i = ; i < cnt; i++) ans[a[now++].id] = X[i] + ;
for(int i = ; i < n; i++) printf("%lld ", ans[i]);
return ;
}/*
*/