(Description)
(L)个点围成一个圆. 我们选定任意一个点作为原点, 则每个点的坐标为从原点顺时针走到这个点的距离. 圆上有(N)只蚂蚁, 分别被编号为(1)到(N). 开始时, 第(i)只蚂蚁在坐标为(X_{i})的点上. 这(N)只蚂蚁同时开始移动. 对于每一只蚂蚁(i), 给定其初始方向(W_{i}:) 假如i开始时是顺时针走的, 则(W_{i})的值为(1); 否则为(2). 每只蚂蚁的速度均为(1). 当某个时刻两只蚂蚁相遇时, 它们都分别都掉头往反方向走.
对于每一只蚂蚁, 请你求出其开始移动(T)秒后的位置.
(Input)
输入格式如下:
(N) (L) (T)
(X_{1}) (W_{1})
(X_{2}) (W_{2})
:
(X_{N}) (W_{N})
(Output)
输出(N)行, 第(i)为(T)秒后第(i)只蚂蚁所在的坐标.
每个坐标都在([0,L−1])之间.
(Sample) (Input) (1)
(3) (8) (3)
(0) (1)
(3) (2)
(6) (1)
(Sample) (Input) (2:)
(4) (20) (9)
(7) (2)
(9) (1)
(12) (1)
(18) (1)
(Sample) (Output) (1:)
(1)
(3)
(0)
(Sample) (Output) (2:)
(7)
(18)
(18)
(1)
(HINT)
样例 (1:) (1.5)秒后, 第(1)和第(2)只蚂蚁在坐标(1.5)处相遇; 一秒后, (1)和(3)在(0.5)处相遇; (0.5)秒后, 也就是开始移动(3)秒后, 三只蚂蚁分别位于坐标(1, 3)和(0).
所有输入均为整数
(1≤N≤105)
(1≤L≤109)
(1≤T≤109)
(0≤X_{1}<X_{2}<⋯<X_{N}≤L−1)
(1≤W_{i}≤2)
思路
这道题是一道思维题
我们首先考虑最麻烦的情况：两只蚂蚁相遇的情况
因为每只蚂蚁的速度都为(1)，所以我们考虑蚂蚁(i)与蚂蚁(j)相遇后，蚂蚁(i)的编号变成(j)，代替蚂蚁(j)继续往前走，蚂蚁(j)同理。
所以蚂蚁的相对位置并不会改变。
我们就可以计算出每只蚂蚁一直向前走最后达到的位置，最后计算出每只蚂蚁在圆圈上的排名，再将(x)排序一遍，每只蚂蚁的排名对应的(x)就是最后的位置
因为蚂蚁的相对位置不会改变，所以我们只用求出(1)只蚂蚁的位置，其他蚂蚁就可以得出
我们考虑蚂蚁(1)
怎么计算蚂蚁(1)的排名(pos)
可以得出
每次有一只蚂蚁从(0)到(L-1)时，(pos--)
每次有一只蚂蚁从(L-1)到(0)时，(pos++)
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int x[N],w[N];
int main()
{
int n,l,t;
scanf("%d %d %d",&n,&l,&t);
for(int i=1;i<=n;i++)scanf("%d %d",&x[i],&w[i]);
int pos=0;
for(int i=1;i<=n;i++)
{
if(w[i]==1)x[i]+=t;//计算一直往前走t分钟后的位置
else x[i]-=t;//逆时针
pos+=x[i]/l;//从L-1到0
if(x[i]%l<0)pos--;//0到L-1
x[i]=(x[i]%l+l)%l;//计算一直走到最后的位置
}
sort(x+1,x+n+1);
pos=(pos%n+n)%n;//蚂蚁1的最后位置
for(int i=pos+1;i<=n;i++)printf("%d
",x[i]);
for(int i=1;i<=pos;i++)printf("%d
",x[i]);
return 0;
}