[思维]Ants on a Circle

题目描述

There is a circle with a circumference of L. Each point on the circumference has a coordinate value, which represents the arc length from a certain reference point clockwise to the point. On this circumference, there are N ants. These ants are numbered 1 through N in order of increasing coordinate, and ant i is at coordinate Xi.

The N ants have just started walking. For each ant i, you are given the initial direction Wi. Ant i is initially walking clockwise if Wi is 1; counterclockwise if Wi is 2. Every ant walks at a constant speed of 1 per second. Sometimes, two ants bump into each other. Each of these two ants will then turn around and start walking in the opposite direction.

For each ant, find its position after T seconds.

Constraints
All input values are integers.
1≤N≤105
1≤L≤109
1≤T≤109
0≤X1<X2<…<XN≤L−1
1≤Wi≤2

 

输入

The input is given from Standard Input in the following format:

N L T
X1 W1
X2 W2
:
XN WN

 

输出

Print N lines. The i-th line should contain the coordinate of ant i after T seconds. Here, each coordinate must be between 0 and L−1, inclusive.

 

样例输入

复制样例数据

3 8 3
0 1
3 2
6 1

样例输出

1
3
0

 

提示

1.5 seconds after the ants start walking, ant 1 and 2 bump into each other at coordinate 1.5. 1 second after that, ant 1 and 3 bump into each other at coordinate 0.5. 0.5 seconds after that, that is, 3 seconds after the ants start walking, ants 1, 2 and 3 are at coordinates 1, 3 and 0, respectively.

 如果在一条直线上来回运动，初始位置最小的1号蚂蚁的坐标在ts后依然是最小的，而在一个圆上运动，当有蚂蚁从L-1运动到0，1号蚂蚁的坐标相对大小++，若有蚂蚁从0运动到L-1，1号蚂蚁的相对坐标大小--

#include <iostream>
#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;

ll n,l,t;
ll ans[100005];

int main()
{
    scanf("%lld%lld%lld",&n,&l,&t);
    ll p=1;
    for(ll i=1;i<=n;i++){
        ll x,w;scanf("%lld%lld",&x,&w);
        if(w==1){
            ans[i]=(x+t)%l;
            p+=(x+t)/l;
        }
        else{
            ans[i]=(x-t)%l;
            p+=(x-t)/l;
            if(ans[i]<0) ans[i]+=l,p--;
        }
    }
    sort(ans+1,ans+1+n);
    p=(p%n+n)%n;
    if(p==0) p=n;
    for(ll i=p;i<=n;i++) printf("%lld\n",ans[i]);
    for(ll i=1;i<=p-1;i++) printf("%lld\n",ans[i]);
    return 0;
}

View Code