AT_agc013_c [AGC013C] Ants on a Circle

FS_NEO · 2025-11-16 12:04:35 · 个人记录

经典的碰撞问题。

每次蚂蚁碰撞后，我们让蚂蚁交换编号，穿过对方继续行走。由于蚂蚁相对位置不变，而最终蚂蚁落在的位置易知，我们只要求出第一只蚂蚁对应 T 时刻序列中第几只蚂蚁。

线上就还是第一只，原上要考虑最后一只蚂蚁走完了一圈的情况。按顺时针编号，蚂蚁每顺时针跨过 0 位置，第一只蚂蚁对应序列中位置就加一，反之亦然。我们不好对每只蚂蚁求跨越 0 的次数，但是总数是好求的。

/*

        2025.11.14

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=300005,inf=0x3f3f3f3f;
int n,l,t,cnt,a[MAXN];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n>>l>>t;
    for(int i=0,x,w;i<n;i++){
        cin>>x>>w,w=(w==1?1:-1);
        x+=t*w;
        cnt=((cnt+(int)floor(1.0*x/l))%n+n)%n;
        a[i]=(x%l+l)%l;
    }
    sort(a,a+n);
    for(int i=0;i<n;i++)cout<<a[(i+cnt)%n]<<"\n";
    return 0;
}