Problem:


Score : 700 points

Problem Statement

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 X_i.

The N ants have just started walking.
For each ant i, you are given the initial direction W_i. Ant i is initially walking clockwise if W_i is 1; counterclockwise if W_i 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 \leq N \leq 10^5

1 \leq L \leq 10^9

1 \leq T \leq 10^9

0 \leq X_1 < X_2 < ... < X_N \leq L - 1

1 \leq W_i \leq 2

Input

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

N L T
X_1 W_1
X_2 W_2
:
X_N W_N

Output

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.

Sample Input 1

3 8 3
0 1
3 2
6 1

Sample Output 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.

Sample Input 2

4 20 9
7 2
9 1
12 1
18 1

Sample Output 2

7
18
18
1



Sample input:
3 8 3
0 1
3 2
6 1


Sample output:
1
3
0

Submission status: Accepted

Solution code:
n, l, t = map(int, input().split())
cor_0 = [list(map(int, input().split())) for _ in range(n)]
cor_t = [(x+t)%l if w == 1 else (x-t)%l for x,w in cor_0]
x0, w0 = cor_0[0]
xt = cor_t[0]
cor_t.sort()


marker = 0
for i in range(1,n):
    if w0 == cor_0[i][1]:
        continue
    
    dist = 2 * t
    if w0 == 1:
        if dist - (cor_0[i][0] - x0) % l >= 0:
            marker += 1
            dist -= (cor_0[i][0] - x0) % l
            marker += dist // l
            if dist % l == 0:
                marker -= 1
    else:
        if dist - (x0 - cor_0[i][0]) % l >= 0:
            marker -= 1
            dist -= (x0 - cor_0[i][0]) % l
            marker -= dist // l

marker %= n
pos_x0 = (cor_t.index(xt) - marker) % n
for i in range(pos_x0, pos_x0+n):
    print(cor_t[i%n])

Submission status: Accepted

Solution code:
# AGC C Ants on a Circle
f=lambda:map(int,input().split())
N,L,T=f()
X,W=[],[]
for _ in [0]*N:
    x,w=f()
    X.append(x)
    W.append(w)
    
if W[0]==2:
    X[0]+=L
    
col=0
for j in range(N):
    if W[j]==W[0]:
        continue
    else:
        if W[0]==1:
            if 2*T-(X[j]-X[0])>=0:
                col+=(1+(2*T-(X[j]-X[0]))//L)
        else:
            if 2*T-(X[0]-X[j])>=0:
                col-=(1+(2*T-(X[0]-X[j]))//L)

col=col%N
X2=[(X[i]+(3-2*W[i])*T) % L for i in range(N)]
X2_0=X2[0]

X2.sort()

index=[i for i,x in enumerate(X2) if x==X2_0]

if len(index)==1:
    index=index[0]
else:
    if W[0]==1:
        index=index[1]
    else:
        index=index[0]

i=(index-col)%N

X2=X2[i:]+X2[:i]
print(*X2,sep='\n')

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/agc013/tasks/agc013_c

蟻がカードを持っていて、すれ違う際にカードを交換すると考える
T秒後にどの蟻がどのカードを持っているか考えればいい

Tが大きいため、良い感じに処理する必要がある
→1周をシミュレートする？
→1周した際の変化を累積させ、最後の余分な時間分を計算すればいい

1週分のシミュレーションには、最悪(N/2)**2 = 2500000000
がかかるので、もっと高速化を考える必要がある

実は1周するにあたり、カードは以下のように動く
>>>> <<<<
7531 2468

>> <<<<
31 24
75   68

つまり、2回かけて1つ後ろに移動する

あとは計算しやすいような工夫を考える
普通に移動経路を時間とともに列挙しようとするとO(LCM(右向き,左向き))かかる

=====答えを見た=====

あまりにシンプルで驚愕
流石AGC…
困った時はいい性質がないか観察することが大事…

カードは必ず昇順に並ぶ？
最初は昇順
→昇順でぶつかったとする
→カードは交換されるので、順序は変わらない！！(すごい)

あとはT秒後の0のカードの位置さえ分かればいい
愚直にやってもできるが…
ぶつかる際、AとA+1が交換される
時計回りのやつは+1される。反時計回りのやつは-1される
→あるアリが持ってる数字はすれ違う回数がわかれば求められる
一周にかかる時間は L//2
残りを良い感じに計算する (二分探索すればO(logN))


WA→LLが奇数なのに/2してるのがまずかったので全部2倍する
"""

from sys import stdin
import bisect
import sys
N,LL,T = map(int,stdin.readline().split())
LL *= 2
T *= 2

R = []
L = []
R2 = []
L2 = []

for i in range(N):
    x,w = map(int,stdin.readline().split())
    x *= 2
    if w == 1:
        R.append((x,i))
        R2.append(x)
        R2.append(x-LL)
    else:
        L.append((x,i))
        L2.append(x)
        L2.append(x+LL)

R2 += [float("-inf"),float("inf")]
L2 += [float("-inf"),float("inf")]
R2.sort()
L2.sort()

ans = [None] * N
for rx,ind in R:

    last = (rx + T) % LL
    plus = ind + (T // (LL//2)) * len(L)
    rem  = T % (LL//2)

    #print (plus,rem,file=sys.stderr)
    #rx以上 re+2*rem未満の数を数えればいい
    #l <= x < rを求めるには r以上最小のind-l以上最小のind
    plus += bisect.bisect_left(L2,rx+2*rem) - bisect.bisect_left(L2,rx)
    ans[plus % N] = last
    #print (plus,last,file=sys.stderr)

for lx,ind in L:

    last = (lx - T) % LL
    plus = ind - (T // (LL//2)) * len(R)
    rem = T % (LL//2)

    #lx以下、le-2*rem超過の数を数えればいい
    #l < x <= r -> l+1 <= x < r+1
    plus -= bisect.bisect_left(R2,lx+1) - bisect.bisect_left(R2,lx-2*rem+1)
    ans[plus % N] = last

if None in ans:
    print (sasasas)

for i in ans:
    print (i//2)

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,L,T = MI()
q,r = T//L,T % L
A = []
a = 0  # 開始時点で、(時計回りの蟻の数)-(半時計まわりの蟻)
for i in range(N):
    x,w = MI()
    a += (-2)*w+3
    for j in range(-1,2):
        A.append(x+r*((-2)*w+3)+j*L)
A.sort()

print(*[A[N+(i+q*a)%N] % L for i in range(N)],sep='\n')

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,L,T = MI()
q,r = T//L,T % L
A = []
a = 0  # 開始時点で、(時計回りの蟻の数)-(半時計まわりの蟻)
for i in range(N):
    x,w = MI()
    if w == 1:
        a += 1
        for j in range(-1,2):
            A.append(x+r+j*L)
    else:
        a -= 1
        for j in range(-1,2):
            A.append(x-r+j*L)
A.sort()
ANS = [A[i] % L for i in range(N,2*N)]
for i in range(N):
    print(ANS[(i+q*a) % N])

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
N, L, T = map(int, input().split())
XW = [tuple(map(int, input().split())) for _ in range(N)]
X = np.array([x for x, w in XW], dtype=int)
W = np.array([(w%2)*2-1 for x, w in XW], dtype=int)
X += W*T
cnt = np.sum(X//L)%N
X %= L
X = sorted(X)
print('\n'.join(map(str, X[cnt:])))
print('\n'.join(map(str, X[:cnt])))

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・順序が固定されるので、区間だったら簡単
・円のときも、地点 0 をそれぞれの方向に通った人数を見れば計算できる
"""

N, L, T = map(int, readline().split())
XW = np.array(read().split(), np.int64)
X = XW[::2]
W = XW[1::2]

speed = np.where(W == 1, 1, -1)

Y = X + speed * T

n = (Y // L - X // L).sum()
n %= N

Y %= L
Y.sort()
Y = np.concatenate((Y[n:], Y[:n]))

print('\n'.join(map(str, Y.tolist())))

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

N,L,T=map(int,input().split())
res=[]
start=[]
for _ in range(N):
    x,w=map(int,input().split())
    start.append((x,w%2))
    res.append(((x+T*(-1)**(w+1))%L,w%2))


res.sort()
#print(res,pos,id)
if start[0][1]==1:
    id=0
    pos=start[0][0]
    for i in range(1,N):
        x,w=start[i]
        if w!=start[0][1]:
            id+=(2*T+pos-x)//L-((pos-x-1)//L)
    id%=N
    ans=[-1]*N
    check=-1
    for i in range(N):
        p,w=res[i]
        if p==(pos+T)%L and w==1:
            ans[i]=id
            check=i
            break
    #print(ans,check)
    for i in range(1,N):
        ans[check-i]=(id-i)%N
    res=[(ans[i],res[i][0]) for i in range(N)]
    #print(ans)
    #print(res)
    res.sort()
    for id,pos in res:
        print(pos)
else:
    id=0
    pos=start[0][0]
    for i in range(1,N):
        x,w=start[i]
        if w!=start[0][1]:
            id-=(2*T+x-pos)//L-((x-pos-1)//L)
    id=id%N
    ans=[-1]*N
    check=-1
    for i in range(N):
        p,w=res[i]
        if p==(pos-T)%L and w==0:
            ans[i]=id
            check=i
            break
    for i in range(1,N):
        ans[check-i]=(id-i)%N
    res=[(ans[i],res[i][0]) for i in range(N)]
    res.sort()
    for id,pos in res:
        print(pos)

Submission status: Accepted

Solution code:
import bisect
n, l, t = map(int, input().split())

plots = []
plots_after = []
for i in range(n):
    x, w = map(int, input().split())
    plots.append((x, w, i))
    if w == 1:
        plots_after.append((x+t) % l)
    else:
        plots_after.append((x-t) % l)
    
x0, w0, _ = plots[0]

if w0 == 1:
    cnt = 0
    for i in range(1, n):
        xi, wi, _ = plots[i]
        if wi == 2:
            cnt += max(0, (2 * t - (xi - x0)) // l + 1)
    cnt %= n

    plots_after.sort()

    x_after = (x0 + t) % l
    idx = bisect.bisect_right(plots_after, x_after)-1

    for i in range(n):
        print(plots_after[(i-cnt+idx) % n])

else:
    cnt = 0
    for i in range(1, n):
        xi, wi, _ = plots[i]
        if wi == 1:
            cnt -= max(0, (2 * t - (l - xi + x0)) // l + 1)
    cnt %= n
    plots_after.sort()

    x_after = (x0 - t) % l
    idx = bisect.bisect_left(plots_after, x_after)

    for i in range(n):
        print(plots_after[(i-cnt+idx) % n])

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, L, T = map(int, input().split())
    M, T = divmod(T, L)
    X = []
    W = []
    for _ in range(N):
        x, w = map(int, input().split())
        X.append(x)
        W.append(w)

    if N == 1:
        if W[0] == 1:
            print((X[0] + T)%L)
        else:
            print((X[0] - T)%L)
        exit()

    Y = []
    for i in range(N):
        if W[i] == 1:
            Y.append(((X[i] + T)%L, 1))
        else:
            Y.append(((X[i] - T)%L, 2))
    Y.sort(key=lambda p: p[0])

    if W[0] == 1:
        y0 = (X[0] + T)%L
        for i in range(N):
            if Y[i][0] == y0:
                i0 = i
                break
        S = 0
        i = 0
        idx = (M * W.count(2) * 2)%N
        while True:
            i = (i+1)%N
            if i:
                S += X[i] - X[i-1]
            else:
                S += L - (X[-1] - X[0])
            if S >= T*2:
                break
            if W[i] == 2:
                idx = (idx+1)%N
        ans = [0] * N
        for i in range(N):
            ans[(idx+i)%N] = Y[(i0+i)%N][0]
    else:
        y0 = (X[0] - T) % L
        for i in range(N-1, -1, -1):
            if Y[i][0] == y0:
                i0 = i
                break
        S = 0
        i = 0
        idx = (-M * W.count(1) * 2)%N
        while True:
            i = (i - 1) % N
            if i != N-1:
                S += X[i+1] - X[i]
            else:
                S += L - (X[-1] - X[0])
            if S >= T * 2:
                break
            if W[i] == 1:
                idx = (idx - 1)%N
        ans = [0] * N
        for i in range(0, -N, -1):
            ans[(idx + i) % N] = Y[(i0+i)%N][0]
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・順序が固定されるので、区間だったら簡単
・円のときも、地点 0 をそれぞれの方向に通った人数を見れば計算できる
"""

N, L, T = map(int, readline().split())
XW = np.array(read().split(), np.int64)
X = XW[::2]
W = XW[1::2]

speed = np.where(W == 1, 1, -1)

Y = X + speed * T

n = (Y // L - X // L).sum()
n %= N

Y %= L
Y.sort()
Y = np.concatenate((Y[n:], Y[:n]))

print('\n'.join(map(str, Y.tolist())))

Submission status: Accepted

Solution code:
n, l, t = map(int,input().split())

c = []
s = 0

for i in range(n):
    x, w = map(int,input().split())
    if w == 1:
        c.append((x+t)%l)
        s += (x+t)//l
    else: # w == 2
        c.append((x-t)%l)
        s += (x-t)//l

c.sort()
s %= n
c = c[s:] + c[:s]
print(*[i for i in c], sep='\n')

Submission status: Accepted

Solution code:
def main():
    N, L, T = map(int, input().split())
    collision = 0
    ants = []
    for i in range(N):
        x, w = map(int, input().split())
        if w == 1:
            collision += (x + T) // L
            a = (x + T) % L
        else:
            collision += (x - T) // L
            a = (x - T) % L
        ants.append(a)
 
    collision %= N
    ants.sort()
    ants = ants[collision:] + ants[:collision]
    for ant in ants:
        print(ant)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, L, T = map(int, readline().split())
    position = []
    #0をL-1からーに時計回りに超える場合は+1
    #0からL-1に反時計回りに超える場合は-1
    count = 0
    for i in range(N):
        x,w = map(int, readline().split())
        if w==1:
            count += (x+T)//L
            position.append((x+T)%L)
        else:
            if x-T<0:
                count += (x-T+1)//L
            position.append((x-T)%L)
    position.sort()
    count %= N
    ans = position[count:] + position[:count]
    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, L, T = map(int, readline().split())
    position = []
    #0をL-1からーに時計回りに超える場合は+1
    #0からL-1に反時計回りに超える場合は-1
    count = 0
    for i in range(N):
        x,w = map(int, readline().split())
        if w==1:
            count += (x+T)//L
            position.append((x+T)%L)
        else:
            if x-T<0:
                count += (x-T)//L
            position.append((x-T)%L)
    position.sort()
    count %= N
    ans = position[count:] + position[:count]
    for i in range(N):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,l,t=f()
X=[0]*n
b=0
for i in range(n):x,w=f();x+=t*(3-2*w);b+=x//l;X[i]=x%l
X.sort()
for i in range(n):print(X[(i+b)%n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n, l, t = map(int, input().split())
XW = [list(map(int, input().split())) for _ in range(n)]
L = []
cnt = 0
for i, xw in enumerate(XW):
  x, w = xw
  L.append((x+t*(3-2*w))%l)
  cnt += (x+t*(3-2*w))//l
L.sort()
for i in range(cnt, cnt+n):
  print(L[i%n])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, l, t = Is()
XW = TIR(n)
ANS = []
count = 0
for x, w in XW:
    if w == 1:
        tmp = (x+t)%l
        count += (x+t)//l
    else:
        tmp = (x-t)%l
        count += (x-t)//l
    ANS.append(tmp)
count %= n
ANS.sort()
ANS = ANS[count:] + ANS[:count]
for ans in ANS:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    N, L, T = map(int, input().split())
    collision = 0
    ants = []
    for i in range(N):
        x, w = map(int, input().split())
        if w == 1:
            collision += (x + T) // L
            a = (x + T) % L
        else:
            collision += (x - T) // L
            a = (x - T) % L
        ants.append(a)

    collision %= N
    ants.sort()
    ants = ants[collision:] + ants[:collision]
    for ant in ants:
        print(ant)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, L, T = list(map(int, input().split(' ')))
    ants = [list(map(int, input().split(' '))) for _ in range(N)]
    # calculate number of ants by which first ant pass
    k = 0
    first_ant = ants[0]
    for a in ants[1:]:
        if first_ant[1] == a[1]:  # same direction
            continue
        if (first_ant[0] > a[0] and a[1] == 1) or (first_ant[0] < a[0] and first_ant[1] == 1):
            d = (max([first_ant[0], a[0]]) - min([first_ant[0], a[0]]))
        else:
            d = (L - max([first_ant[0], a[0]]) + min([first_ant[0], a[0]]))
        k += max([(2 * T - d) // L + 1, 0])
    k %= N
    # ants final locations
    ants_final_loc = [(a[0] + T * (1 if a[1] == 1 else -1)) % L for a in ants]
    first_ant_final_loc = ants_final_loc[0]
    first_ant_final_num = k if first_ant[1] == 1 else (- k) % N
    ants_final_loc.sort()
    # answer
    offsets = [i for i in range(N) if ants_final_loc[i] == first_ant_final_loc]
    offset = offsets[0]
    if len(offsets) > 1 and first_ant[1] == 1:
        offset = offsets[1]
    ants_loc = [ants_final_loc[(i + offset - first_ant_final_num) % N] for i in range(N)]
    for loc in ants_loc:
        print(loc)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, l, t = map(int,input().split())
ants = [tuple(map(int,input().split())) for _ in range(n)]
y = [(x + t * ((m + 1) % 3 - 1)) % l for x, m in ants]
fy = y[0]
y.sort()
firx, firm = ants[0]
c = 0
for x, m in ants:
  if firm != m:
    if firm == 1:
      c += max(-1, 2 * t - x + firx) // l + 1
    else:
      c += max(-1, 2 * t - l + x - firx) // l + 1
iy = (c if firm == 1 else -c) % n
if firm == 1:
  for i in range(n-1, -1, -1):
    if y[i] == fy:
      pi = (i - iy) % n
      break
else:
  for i in range(n):
    if y[i] == fy:
      pi = (i - iy) % n
      break
al = y[pi:] + y[:pi]
print(*al, sep='\n')

Submission status: Accepted

Solution code:
n, l, t = map(int, input().split())
ants = [tuple(map(int, input().split())) for _ in range(n)]

def dist(x, y, sign_0):
    if sign_0 == -1:
        x, y = y, x
    if x < y: return y - x
    else: return y - x + l

place = []
for i, (x, w) in enumerate(ants):
    sign = 1 if w == 1 else -1
    place.append((x + t * sign) % l)
    if i == 0:
        num = 0
        x_0 = x
        sign_0 = sign
    elif sign_0 * sign == -1:
        length = 2 * t
        d = dist(x_0, x, sign_0)
        if length > d or (length == d and sign_0 == -1):
            num = (num + sign_0) % n
            length -= d
            num = (num + (length // l) * sign_0) % n
            if length % l == 0 and sign_0 == 1:
                num = (num - 1) % n
    else: continue

place.sort()
i_0 = (place.index((x_0 + t * sign_0) % l) - num) % n
place.count((x_0 + t * sign_0) % l)

for i in range(i_0, n + i_0):
    i = i % n
    print(place[i])

Submission status: Accepted

Solution code:
n,l,t=map(int,input().split())
xw=[list(map(int,input().split()))for _ in range(n)]
p=[(xw[i][0]+((1 if xw[i][1]==1 else -1)*t))%l for i in range(n)]
p.sort()
ans=0
for x,w in xw:
  if w==1:
    ans+=(x+t)//l
  else:
    ans-=((l-1)-x+t)//l
ans%=n
p=p[ans:]+p[:ans]
print(*p)

Submission status: Accepted

Solution code:
n,l,t = map(int,input().split())
c = []
s = 0
for i in range(n):
  x,w = map(int,input().split())
  if w == 1:
    c.append((x+t)%l)
    s += (x+t)//l
  else:
    c.append((x-t)%l)
    s += (x-t)//l
    
c.sort()
s %= n
c = c[s:] + c[:s]
print(*[i for i in c], sep='\n')

Submission status: Accepted

Solution code:
import bisect

n,l,t = map(int, input().split())
xw = [list(map(int, input().split())) for i in range(n)]
clockwise = []
anticlockwise = []
ans = [None] * n
for key,(x,w) in enumerate(xw):
    if w == 1:
        clockwise.append((x,key))
    else:
        anticlockwise.append((x,key))

len_c = len(clockwise)
len_a = len(anticlockwise)
for key,(x,w) in enumerate(xw):
    if w == 1:
        tmp = bisect.bisect_right(anticlockwise, ((2*t+x)%l,1000000)) - bisect.bisect_right(anticlockwise,(x,0))
        lap = (x+2*t) // l
        num = (key + tmp + lap * len_a) % n
        ans[num] = (x + t) % l
    else:
        tmp = bisect.bisect_left(clockwise, (x,-1)) - bisect.bisect_left(clockwise, ((x-2*t)%l,-1))
        lap = (x-2*t) // l
        num = (key - tmp + lap * len_c) % n
        ans[num] = (x - t) % l

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
N, L, T = map(int, input().split())
X = [0] * N
W = [0] * N
for i in range(N):
    X[i], W[i] = map(int, input().split())

res = [0] * N
c = 0
for i in range(N):
    if W[i] == 1:
        res[i] = (X[i] + T) % L
        c += (X[i] + T) // L
    else:
        res[i] = (X[i] - T) % L
        c += (X[i] - T) // L
res = sorted(res)
c = c % N
res = res[c:] + res[:c]
print(*[ans for ans in res], sep='\n')

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline

N,L,T = MI()
for_l = []
rev_l = []
final = []
for i in range(N):
    if i==0:
        x0,w0 = MI()
        x,w = x0,w0
    else:
        x,w = MI()
    if w==1:
        for_l += [x]
        final += [(x+T)%L]
    else:
        rev_l += [x]
        final += [(x-T)%L]

final.sort()
opposite_l = rev_l if w0==1 else for_l
opp_num = len(opposite_l)
cicle = (2*T)//L
res = (2*T)%L
cnt = 0 #i=1のアリが衝突する回数
cnt += opp_num*cicle
if res!=0 and res!=1:
    xr = (x0 + res -1)%L if w0==1 else x0
    xl = x0 if w0==1 else (x0-res+1)%L
    for i in opposite_l:
        if xl<=xr and xl<=i<=xr:
            cnt += 1
        if xl>xr and (i>=xl or i<=xr):
            cnt += 1
c = (cnt)%N if w0==1 else (-cnt)%N #x0+Tにくるアリの番号
if w0==1:
    c_idx = final.index((x0+T)%L)
else:
    c_idx_l = [i for i,v in enumerate(final) if v==(x0-T)%L]
    c_idx = c_idx_l[-1]
ans = [-1 for i in range(N)]
ans[c] = final[c_idx]
for i in range(1,N):
    ans[(c+i)%N] = final[(c_idx+i)%N]
[print(x) for x in ans]

Submission status: Accepted

Solution code:
n,l,t=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=[]
cnt=0

for i in range(n):
  tmp=arr[i][0]  #蟻iの最初の座標
  # 衝突を考慮しなかった場合の各蟻のt秒後の座標をtmpに入れる
  # cntには円を周回した回数の合計値を入れる
  if arr[i][1]==1:
    tmp+=t
    tmp%=l
    cnt+=(arr[i][0]+t)//l
  else:
    tmp-=t
    tmp%=l
    cnt+=(arr[i][0]-t)//l
  ans.append(tmp)
ans=sorted(ans) #ansに格納したtmp（座標）を昇順にソート
cnt%=n #0番目目の蟻の衝突回数
tmp=[0]*n
for i in range(n):
  #初期位置0番目の蟻の最終位置は、原点から見て衝突数番目の位置にいるはず
  #各蟻の位置関係は、衝突を繰り返すので変わらず時計回りに位置するはず
  tmp[i]=ans[(cnt+i)%n]
ans=tmp
for pos in ans:
  print(pos)

Submission status: Accepted

Solution code:
N, L, T=map(int, input().split())
XW=[list(map(int, input().split())) for _ in range(N)]
X_=[(XW[i][0]+T)%L if XW[i][1]==1 else (XW[i][0]-T)%L for i in range(N)]
X_.sort()
A0_=(XW[0][0]+T)%L if XW[0][1]==1 else (XW[0][0]-T)%L
P0_=X_.index(A0_)
if P0_>0:
    X_=X_[P0_:]+X_[:P0_]
    
if XW[0][1]==1:
    C0_=round(sum([(T-(XW[i][0]-XW[0][0])/2)//(L/2)+1 if XW[i][1]!=1 and (XW[i][0]-XW[0][0])/2<=T else 0 for i in range(1, N)])%N)
else:
    C0_=round(N-sum([(T-(XW[0][0]+L-XW[i][0])/2)//(L/2)+1 if XW[i][1]!=2 and (XW[0][0]+L-XW[i][0])/2<=T else 0 for i in range(1, N)])%N)
    
if N>1 and X_[0]==X_[1] and XW[0][1]==1:
  C0_=round((C0_-1)%N)

if C0_>0:
  X_=X_[N-C0_:]+X_[:N-C0_]

print(*X_, sep='\n')

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
N,L,T = LI()
X = []
W = []
for _ in range(N):
    x,w = LI()
    X.append(x)
    W.append(1 if w == 1 else -1)

# 最終の位置計算
Y = []
for i in range(N):
    y = (X[i] + T * W[i]) % L
    Y.append(y)

# 蟻1が何回すれ違うか
r = T // L
m = T % L

kai = r * W.count(-W[0]) * 2

# m秒以内にすれ違う蟻
for i in range(1,N):
    if W[0] != W[i]:
        d = ((X[i] - X[0]) * W[0]) % L
        if d < m * 2:
            kai += 1
            if (L - d) < (m - d) * 2:
                kai += 1

# Y[0]のNoを求める
Num = (kai * W[0]) % N

# Yをソート
y0 = Y[0]
Y.sort()
p = Y.index(y0)
if W[0] > 0:
    p = bisect.bisect_left(Y,y0)
else:
    p = bisect.bisect_right(Y, y0) - 1
s = (p-Num) % N

for _ in range(N):
    print (Y[s])
    s = (s + 1) % N

Submission status: Accepted

Solution code:
n,l,t=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=[]
cnt=0
for i in range(n):
  tmp=arr[i][0]
  if arr[i][1]==1:
    tmp+=t
    tmp%=l
    cnt+=(arr[i][0]+t)//l
  else:
    tmp-=t
    tmp%=l
    cnt+=(arr[i][0]-t)//l
  ans.append(tmp)
ans=sorted(ans)
cnt%=n
tmp=[0]*n
for i in range(n):
  tmp[i]=ans[(cnt+i)%n]
ans=tmp
for pos in ans:
  print(pos)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, L: int, T: int, X: "List[int]", W: "List[int]"):
    

    nxtX = [0] * N
    r = 0
 
    
    #基準より前にいるやつで逆のやつがいたら遠さからrをカウント
    for i in range(N):
        if W[i]==1:
            nxtX[i]=(X[i]+T)%L
            r+=(X[i]+T)//L      
        else:
            nxtX[i]=(X[i]-T)%L
            r+=(X[i]-T)//L

    nxtX.sort()


    r%=N
    
    
    ans=nxtX[r:]+nxtX[:r]
    print("\n".join(map(str,ans)))
    return
    

                



# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    L = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    X = [int()] * (N)  # type: "List[int]"
    W = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        X[i] = int(next(tokens))
        W[i] = int(next(tokens))
    solve(N, L, T, X, W)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""

AtCoder Grand Contest 013 C - Ants on a Circle
https://atcoder.jp/contests/agc013/tasks/agc013_c

おなじみの蟻の問題と同じく、ぶつかる＝すれ違ったと考えることができる。
円形なので、最初に隣り合っている蟻としかぶつからない

また、一周して元の位置に戻ってくるみたいなことも起こりうる
・全員同じ向き
ぶつからないので、移動距離をそのまま計算
・一匹でも向き違いがいる場合
すれ違ったと考えていい。その際二匹の番号が入れ替わるようなイメージ。
　- ある蟻の番号が決まれば他の蟻の番号も初期の位置関係から決められるが？
　- どの蟻の番号が決まればいい？
　- 原点の通行量で考える
　- T秒後に差し引きで右から左に２匹いどうしたら、1,2,3,4,...,Nが、　3,4,5,6,...,N,1,2　になっているということ。
　- なので、T秒後の位置を求めて、原点における左右の通行量分ずらしてあげるとよい

"""



N,L,T = map(int, input().split())

nxtX = [0] * N
cnt_LR = 0

for i in range(N):
    x,w = map(int, input().split())

    if w == 1:
        nxtX[i] = (x + T) % L
        cnt_LR += (x + T) // L

    else:
        """
        -13 % 3 = 3 * (-5) + 2 的な感じで商が負で余りが正
        """
        nxtX[i] = (x - T) % L
        cnt_LR += (x - T) // L

nxtX.sort()
# 全体で一周していると効果0なので、ずれの分を求める。これは正の値にしかならない
# 正なので、右にいくらずれているか
cnt_LR %= N
"""
1,2,3,4,5,6,7,8 -> 7,8,1,2,3,4,5,6 みたいなずれ方を、[1~6] + [7,8]とするみたいな感じ
"""
ans = nxtX[cnt_LR:] + nxtX[:cnt_LR]
for n in ans:
    print(n)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, L, T = map(int, input().split())
gap = 0
X = [0] * N
for i in range(N):
    x, w = map(int, input().split())
    x += (-2*w+3) * T 
    gap += x // L
    X[i] = x % L
X.sort()
for i in range(N):
    print(X[(i+gap) % N])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N, L, T= map(int,input().split())
X = []
W = []

for i in range(N):
    x,w = map(int,input().split())
    X.append(2*x)
    W.append(2*(1-w)+1)

pos = [((x+2*T*w) % (2*L))//2 for x,w in zip(X,W)]

meet = 0
for i in range(1,N):
    if W[0] != W[i]:
        if W[0] == 1:
            R = 2*T - (X[i] - X[0])//2
        else:
            R = 2*T - (2*L - (X[i] - X[0]))//2
        if R >= 0:
            meet += 1 + R//L
M = (meet * W[0]) % N

aM_pos = pos[0]
pos.sort()

aM_idx = pos.index(aM_pos)
if pos.count(aM_pos) == 2 and W[0] == 1:
    aM_idx += 1

a0_idx = (aM_idx-M) % N
ans = pos[a0_idx:]+pos[:a0_idx]

for ant in ans:
    print(ant)

Submission status: Accepted

Solution code:
n,l,t=map(int,input().split())
inf=[]
s=0
for _ in range(n):
   x,y=map(int,input().split())
   if y==1:
       x+=t
   else:
       x-=t
   inf.append(x%l)
   s+=x//l
inf.sort()
for i in range(n):
    print(inf[(i+s)%n])

Submission status: Accepted

Solution code:
N,L,T = map(int,input().split())
x,w = map(int,input().split())
D = []
m = 0
def f(x,w):
    if w == 1:
        a = (x+T) % L
        return a
    else:
        a = (x-T) % L
        return a
for i in range(2,N+1):
    X,W = map(int,input().split())
    a = f(X,W)
    if f(X,W) < f(x,w):
        a += L
    D.append(a)
    if w != W:
        if w == 1:
            l = (X - x)%L
        else:
            l = (x - X)%L
        if l <= 2*T:
            t = (2*T - l)//L + 1
            if (2*T - l)%L == 0:
                if w == 1:
                    t -= 1
        else:
            t = 0
        m += t
if w == 1:
    p = m%N + 1
else:
    p = (1-m)%N
    if p == 0:
        p = N
D.sort()
dic = {}
dic[p] = f(x,w)
for i in range(N-1):
    p += 1
    if p > N:
        p -= N
    q = D[i]
    dic[p] = q%L
for i in range(1,N+1):
    print(dic[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, L, T = map(int, input().split())
gap = 0
X = [0] * N
for i in range(N):
    x, w = map(int, input().split())
    x += ((w + 1) % 3 - 1) * T
    gap += x // L
    gap %= N
    X[i] = x % L
X.sort()
for i in range(N):
    print(X[(i+gap) % N])

Submission status: Accepted

Solution code:
N, L, T = map(int, input().split())
gap = 0
X = [0] * N
for i in range(N):
    x, w = map(int, input().split())
    x += ((w + 1) % 3 - 1) * T
    gap += x // L
    gap %= N
    X[i] = x % L
X.sort()
for i in range(N):
    print(X[(i+gap) % N])

Submission status: Accepted

Solution code:
N, L, T = map(int, input().split())
X = []
W = []
for _ in range(N):
    x, w = map(int, input().split())
    X.append(x)
    if w == 2:
        w = -1
    W.append(w)

C = 0
for i in range(1, N):
    if W[i] != W[0]:
        C += T // (L / 2)
        if W[0] == 1:
            D = X[i] - X[0]
        else:
            D = X[0] + L - X[i]
        if T % (L / 2) * 2 >= D:
            C += 1

for i in range(N):
    X[i] = (X[i] + T * W[i]) % L

x = X[0]

X.sort()

ng = -1
ok = N
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if X[mid] >= x:
        ok = mid
    else:
        ng = mid
if W[0] == 1 and ok < N-1:
    if X[ok] == X[ok+1]:
        ok += 1

start = int((ok - C * W[0]) % N)
for i in X[start:]:
    print(i)
for i in X[:start]:
    print(i)