专栏文章

AT_agc013_c [AGC013C] Ants on a Circle

FFS_NEO
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min73a2g
此快照首次捕获于
2025/12/01 21:38
3 个月前
此快照最后确认于
2025/12/01 21:38
3 个月前
查看原文
经典的碰撞问题。
每次蚂蚁碰撞后，我们让蚂蚁交换编号，穿过对方继续行走。由于蚂蚁相对位置不变，而最终蚂蚁落在的位置易知，我们只要求出第一只蚂蚁对应 TT 时刻序列中第几只蚂蚁。
线上就还是第一只，原上要考虑最后一只蚂蚁走完了一圈的情况。按顺时针编号，蚂蚁每顺时针跨过 00 位置，第一只蚂蚁对应序列中位置就加一，反之亦然。我们不好对每只蚂蚁求跨越 00 的次数，但是总数是好求的。
CPP
/*

		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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...