[??记录]CF652F Ants on a Circle

**题意** ： 在一个长度为 $m$ 的圆环上有 $n$ 只初始位置互不相同的蚂蚁，每只蚂蚁的速度都为 $1$ ，初始方向为顺时针或逆时针。 两只运动方向不同的蚂蚁相遇时会调转方向（相遇位置不一定是整数），问 $t$ 时间后每只蚂蚁的位置。 $n\leq 3\times 10^5,m\leq 10^9$ ，时限$\texttt{2s}$。 ------------ 我们假设蚂蚁在碰撞时穿过对方，那么就能得到最终哪些位置上有蚂蚁。 显然，所有蚂蚁标号的相对顺序是不变的，现在只需再确定某个蚂蚁的标号，或者某个标号的排名。 可以考虑过程中有多少个蚂蚁穿过了位置 $0$ ，若顺时针穿过一次，可以看做左侧插入一只蚂蚁，若逆时针穿过，可以看做左侧消失一只蚂蚁。 （这个做法的妙处是，事件“某只蚂蚁穿过”不需要确知其编号） 若某只蚂蚁顺时针移动，且初始位置为 $x_i$ ，则穿过 $0$ 的次数为 $\lfloor (x_i+t)/m\rfloor$。 若某只蚂蚁逆时针移动，且初始位置为 $x_i$ ，则穿过 $0$ 的次数为 $\lceil (t-x_i)/m\rceil$。 由此不难得到最左侧蚂蚁的编号。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define pb push_back #define MaxN 305000 using namespace std; int read(){ int X=0;char ch=0; while(ch<48||ch>57)ch=getchar(); while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar(); return X; } char readc(){ char ch=0; while(ch<'A'||ch>'Z')ch=getchar(); return ch; } struct Data{int p,id;bool d;}a[MaxN]; bool cmp(const Data &A,const Data &B) {return A.p==B.p ? a[A.id].d : A.p<B.p;} int n,m,p1[MaxN],ans[MaxN]; ll t; int main() { n=read();m=read();scanf("%lld",&t); int cnt=0; for (int i=1;i<=n;i++){ a[i].p=read()-1; a[i].d=(readc()=='R'); a[i].id=i; }sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++){ if (a[i].d){ ll det=a[i].p+t; cnt=(cnt+det/m)%n; }else { ll det=t-a[i].p; cnt=(cnt-(det+m-1)/m)%n; }p1[i]=a[i].d ? (a[i].p+t)%m : (a[i].p+m-t%m)%m; }sort(p1+1,p1+n+1); cnt=(cnt+n)%n; for (int i=1;i<=n;i++) ans[a[(i-cnt-1+n)%n+1].id]=p1[i]; for (int i=1;i<=n;i++)printf("%d ",ans[i]+1); return 0; } ```