题解 AT2369【 [AGC013C] Ants on a Circle】 思维题

· · 题解

考虑到原来每只蚂蚁都在相邻之间撞来撞去，所以肯定最后每只蚂蚁的相对顺序是不会改变的。显然可以直接确定最后位置的整个序列，只要确定 1 号蚂蚁在序列的位置（最终编号），就可以知道每只蚂蚁最后实际的位置。

不妨想象成蚂蚁相撞，蚂蚁相互穿过，编号交换。 i 号蚂蚁的实际位置应当在拥有 i 编号的蚂蚁的位置。

考虑在直线上的情况，直接对应就行了。但现在是在环上，如果有一只蚂蚁逆时针经过 0 ，那么 1 号蚂蚁最后的位置就会向前一位，顺时针则会向后一位。(想象成这只蚂蚁变成了负数，那么在直线上，他应该是最前面的，但先在在环上，所以他穿过去了，就会变成最后面的，所以原来在他后面的都会往前挪一位）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, l, t, ans[N]; 
int main() {
    scanf("%d%d%d", &n, &l, &t);
    int cnt = 0;
    for(int i = 0, x, w; i < n; i++){
        scanf("%d%d", &x, &w);
        x += ((w == 1) ? t : -t);
        cnt = ((cnt + (int)floor(1.0 * x / l)) % n + n) % n; 
        ans[i] = (x % l + l) % l;
    }
    sort(ans, ans + n);
    for(int i = 0; i < n; i++)
        printf("%d\n", ans[(cnt + i) % n]); 
    return 0;
}