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: Runtime Error

Solution code:
N, L, T = list(map(int, input().split()))

X = []
W = []
X_after = []
for _ in range(N):
    x, w = list(map(int, input().split()))
    if w == 1:
        x_after = (x + T) % L
    else:
        x_after = (x - T) % L

    if x_after < 0:
        x_after = L + x_after

    X.append(x)
    W.append(w)
    X_after.append(x_after)

n_colide = 0
for i in range(1, N):
    if W[0] == 1 and W[i] == 2:
        dist = X[i] - X[0]
        n_colide += 2 * (T - (dist / 2)) // L + 1
    elif W[0] == 2 and W[i] == 1:
        dist = (L + X[0]) - X[i]
        n_colide += 2 * (T - (dist / 2)) // L + 1

if W[0] == 1:
    num_after = W[0] + (N % n_colide)
else:
    num_after = W[0] - (N % n_colide)
    num_after = num_after if num_after >= 0 else L + num_after

num_after = int(num_after)

last_info = [
    {"X": X_after[0], "num": num_after}
]

for i in range(1, N):
    num = num_after + i
    if num >= N:
        num = N - num
    last_info.append({
        "X": X_after[i],
        "num": num,
    })

sorted_info = sorted(last_info, key=lambda info: info["num"])

for info in sorted_info:
    print(info["X"])

Submission status: Runtime Error

Solution code:
import sys

sys.stdin = open('c2.in')
# sys.stdin = open('gen_c/c10.in')


def solve_it_large(n, l, t, x, w):
    ants = []
    for i in range(n):
        ants.append([x[i], w[i], (x[i] + w[i] * t) % l, i])
    # ants.sort()

    n_intersections = 0
    x0, w0, dest0, i0 = ants[0]
    for x, w, dest, i in ants:
        if w != w0:
            d = (w0 * (x - x0) + l) % l
            intersections = 0
            if 2 * t >= d:
                intersections = (2 * t - d) // l + 1
            n_intersections += intersections

    res = [0] * n
    shift = n_intersections
    for i in range(n):
        res[ants[(i + w0 * shift) % n][3]] = ants[i][2]
    return res


def solve_it_chameleons(n, l, t, x, w):
    initial_color = [i for i in range(n)]

    chameleons = [[x[i], w[i], initial_color[i]] for i in range(n)]
    initial_color_clockwise = [chameleons[i][2] for i in range(n)]

    x0, w0, color0 = chameleons[0]
    for i in range(n):
        if w[i] != w0:
            d = (w0 * (x[i] - x0)) % l
            meet = 0
            if 2 * t >= d:
                meet = (2 * t - d) // l + 1
            color0 += w0 * meet
            color0 %= n

    # The chameleon (let's call him chameleon 0) initially at x0 is at (x0 + w0 * t) % l at the end,
    # Initially, its color is color0 and it changed <meet> times.
    # The final clockwise colors are a translation of the initial clockwise colors.

    x_final = [(x[i] + w[i] * t) % l for i in range(n)]
    x_final.sort()
    i = x_final.index((x0 + w0 * t) % l)
    if i + 1 < n and x_final[i] == x_final[i + 1]:
        if w0 == 1:
            i += 1
    res = [0] * n
    for k in range(n):
        color = (color0 + k) % n
        res[color] = x_final[(i+k) % n]
    return res


if __name__ == '__main__':

    n, l, t = map(int, input().split())
    x = []
    w = []
    for i in range(n):
        _x, _w = map(int, input().split())
        if _w == 2:
            _w = -1
        x.append(_x)
        w.append(_w)

    res = solve_it_chameleons(n, l, t, x, w)
    for i in range(n):
        print(res[i])

Submission status: Runtime Error

Solution code:

# アリ１からNまでの前後関係は不変。つまり、アリ１からNまでの順番は保たれる。
# アリの最終座標の昇順リストを用意して、アリ１からNに対応させればよい。

n,l,t=map(int,input().split())
x=[0 for i in range(n+1)]
w=[0 for i in range(n+1)]
ans=[]　# アリの最終座標リスト
w1=[]　# w=1のアリの初期座標リスト
w2=[]　# w=2のアリの初期座標リスト

for i in range(1,n+1):
    x[i],w[i]=map(int,input().split())
    if w[i]==1: a=(x[i]+t)%l; w1.append(x[i])
    if w[i]==2: a=(x[i]-t+l)%l; w2.append(x[i])
    ans.append(a)

# kはアリ同士がすれ違った数
k=0
for i in range(n):
    if w[i]==1:　# もしw=1のアリがいないならk=0のままで問題なし。
        if (x[i]+2*t)>=l:
            for j in range(x[i],x[i]+2*t+1): k+=w2.count(j)
            for j in range((x[i]+2*t+1)%l,x[i]): k+=w2.count(j)
        else:
            for j in range(x[i],x[i]+2*t+1): k+=w2.count(j)
        break　# １つw=1のアリ見つけたらそこで終了。

# ansをソートしてkだけ円順列的にずらして出力
ans.sort()
for i in range(n): print(ans[(i+k)%n])

Submission status: Runtime Error

Solution code:
N, L, T = list(map(int, input().split(" ")))

# N,L,T = 3,10,6
# a = [1,2,3]
# b = [2,1,1]

a = []
b = []
for i in range(N):
    an, ve = map(int, input().split(" "))
    a.append(an)
    b.append(ve)

crash = 0

for i in range(1, N):
    if b[0] != b[i]:
        if b[0] == 1:
            crash += (T - ((a[i] - a[0]) / 2)) // (L / 2) + 1
        else:
            crash += (T - (L - (a[i] - a[0])) / 2) // (L / 2) + 1

for i in range(N):
    if b[i] == 1:
        a[i] += T
    else:
        a[i] -= T
    a[i] %= L


if b[0] == 1:
    where = int(crash) % N
else:
    where = int(-crash) % N

nowplace = a[where]
a.sort()

if b[0] == 1:
	if crash % 2 == 1:
		where0 = min([i for i in range(N) if a[i] == nowplace])
	else:
		where0 = max([i for i in range(N) if a[i] == nowplace])		
else:
	if crash % 2 == 1:
		where0 = max([i for i in range(N) if a[i] == nowplace])
	else:
		where0 = min([i for i in range(N) if a[i] == nowplace])

where0 = (where0 - crash) % N

res = a[where0:] + a[:where0]
res = map(str, res)

for i in res:
    print(i)

Submission status: Runtime Error

Solution code:
# N:ありの頭数　L:周の長さ　T:時間。この時の状態を求める
N, L, T = list(map(int, input().split()))

ant = [list(map(int, input().split())) for i in range(N)]

line_pos = []
for i in range(0, N):
    if ant[i][1] == 1:
        line_pos.append(ant[i][0] + T)
    else:
        line_pos.append(ant[i][0] - T)
# X1についてのみみる
if ant[0][1] == 1:
    crash_count = 0
    for i in range(1, N):
        if ant[i][1] == 2:
            crash_count += (2 * T - ant[i][0] + ant[0][0]) // L + 1
else:
    crash_count = 0
    for i in range(1, N):
        if ant[i][1] == 1:
            crash_count += (2 * T - ant[i][0] + ant[0][0]) // L + 1
ans_pos = [-1 for i in range(N)]
if ant[0][1] == 1:
    for i in range(0, N):
        if crash_count + i < N:
            ans_pos[crash_count + i] = line_pos[i] % L
        else:
            ans_pos[crash_count + i - N] = line_pos[i] % L
else:
    for i in range(0, N):
        if 0 < i - crash_count:
            ans_pos[N - (i - crash_count)] = line_pos[i] % L
        else:
            ans_pos[i - crash_count] = line_pos[i] % L

for ans in ans_pos:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy import inf
n,l,t = list(map(int,input().split()))
x_list = list()
w_list = list()

for i in range(n):
    x, w = list(map(int,input().split()))
    x_list.append(x)
    w_list.append(w)

d_list = list()
for i in range(len(x_list)-1):
    d_list.append(x_list[i+1]-x_list[i])
d_list.append(x_list[0]+l-x_list[-1])

w_list = [w if w == 1 else -1 for w in w_list]

x_array = np.array(x_list)
w_array = np.array(w_list)
d_array = np.array(d_list)



time = 0
while time < t:
#     s_list = list()
#     # さが縮まるかどうか。縮まるなら1
#     for i in range(len(w_list)):
#         if w_array[i%n] == 1 and w_array[(i+1)%n]==-1:
#             s_list.append(1)
#         elif w_array[i%n] == -1 and w_array[(i+1)%n]==1:
#             s_list.append(-1)
#         else:
#             s_list.append(0)
    
    s_array = (w_array[1:] - w_array[:-1]) * (-1/2)
    s_array = np.append(s_array,(w_array[0]-w_array[-1])*(-1/2))
#     s_array = np.array(s_list)
    # d_arrayには差が入っている。
    butukaru_array = d_array / (s_array*2)
    butukaru_array[butukaru_array == inf] = 0
    if s_array.all == 0:
        next_time = t -time
    else:
        next_time = butukaru_array.max()

    time += next_time
        
    if time >= t:
        next_time -= (time-t)
    
    x_array = (x_array + w_array*next_time)%l
    d_array = d_array - s_array*2*next_time
    
    butukatta_x = np.where(d_array == 0)[0]
    
#     for i in butukatta_x:
    w_array[butukatta_x] *= -1
    w_array[(butukatta_x+1)%n] *= -1
    
for x in x_array:

    while x<0:
        x += l
    while x >= l:
        x -= l
        
    print(int(x))

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, l, t = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n))
    for i in xrange(1, n * 2, 2):
        if dat[i] == 2:
            dat[i] = -1
    t %= l
    y = [(dat[i*2] + t * dat[i*2+1]) % l for i in xrange(n)]
    po = dat[0] * 2
    di = dat[1]
    pu = [[], [], []]
    for i in xrange(n):
        pu[dat[i*2+1]].append(dat[i*2] * 2)
    l *= 2
    pu[-1] += [x + l for x in pu[-1]]
    pu[-1] = pu[-1][::-1]
    pu[1] += [x + l for x in pu[1]]
    pu[1] = [x - 2 * l for x in pu[1]]
    if di == -1:
        pu[-1].pop()
    tt = 0
    t *= 2
    while tt < t:
        x = pu[-di].pop() - di * tt
        k = di * (x - po) / 2
        if tt + k < t:
            po += di * k
        else:
            po += di * (t - tt)
            break
        tt += k
        di = -di
    po = (po % l) / 2
    for i, x in enumerate(y):
        if po == x:
            break
    y = y[i:] + y[:i]
    for x in y:
        print x
main()

Submission status: Runtime Error

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, l, t = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * n))
    for i in xrange(1, n * 2, 2):
        if dat[i] == 2:
            dat[i] = -1
    t %= l
    y = [(dat[i*2] + t * dat[i*2+1]) % l for i in xrange(n)]
    po = dat[0] * 2
    di = dat[1]
    pu = [[], [], []]
    for i in xrange(n):
        pu[dat[i*2+1]].append(dat[i*2] * 2)
    l *= 2
    pu[-1] += [x + l for x in pu[-1]]
    pu[-1] = pu[-1][::-1]
    pu[1] += [x + l for x in pu[1]]
    pu[1] = [x - 2 * l for x in pu[1]]
    pu[di].pop()
    tt = 0
    t *= 2
    while tt < t:
        x = pu[-di].pop() - di * tt
        k = di * (x - po) / 2
        if tt + k < t:
            po += di * k
        else:
            po += di * (t - tt)
            break
        tt += k
        di = -di
    po = (po % l) / 2
    for i, x in enumerate(y):
        if po == x:
            break
    y = y[i:] + y[:i]
    for x in y:
        print x
main()

Submission status: Runtime Error

Solution code:
import numpy as np

n,l,t = map(int, input().split(' '))
x,w = [],[]
x1,x2 = [],[]
for _ in range(n):
    x_,w_ = map(int, input().split(' '))
    x.append(x_)
    w.append(w_)
    if w_ == 1:
        x1.append(x_)
    elif w_ == 2:
        x2.append(x_)

x_ = np.array(x)
w_ = np.array(w)
final_x = (x_+(-w_*2+3)*t)%l

t1 = t % (2*l)
t2 = t // (2*l)
meet = t2*(len(x1)*len(x2))

x1_ = np.array([x1])
x2_ = np.array([x2]).T
d = x2_-x1_
d %= l
meet += np.sum(d <= (2*t1))
meet %= n
ret = np.roll(final_x,-meet)
for ret_ in ret:
    print(ret_)

Submission status: Runtime Error

Solution code:
import numpy as np

n,l,t = map(int, input().split(' '))
x,w = [],[]
x1,x2 = [],[]
for _ in range(n):
    x_,w_ = map(int, input().split(' '))
    x.append(x_)
    w.append(w_)
    if w_ == 1:
        x1.append(x_)
    elif w_ == 2:
        x2.append(x_)

x_ = np.array(x)
w_ = np.array(w)
final_x = (x_+(-w_*2+3)*t)%l

t1 = t % (2*l)
t2 = t // (2*l)
meet = t2*(len(x1)*len(x2))

x1_ = np.array([x1])
x2_ = np.array([x2]).T
d = x2_-x1_
d %= l
meet += np.sum(d <= (2*t1))
meet %= n
ret = final_x[meet:]+final_x[:meet]
for ret_ in ret:
    print(ret_)

Submission status: Runtime Error

Solution code:

ant_list = []   # (pos, direction)

N, L, T = list(map(int, input().split()))
for i in range(N):
    pos, direction = list(map(int, input().split()))
    ant_list.append(Ant(pos, direction))

for t in range(T):
    clide_ant_list = get_colide_ants(ant_list)
    for ant in colide_ant_list:
        ant.change_direction()

    for ant in ant_list:
        ant.move()

    clide_ant_list = get_colide_ants(ant_list)
    for ant in colide_ant_list:
        ant.change_direction()
        ant.move()

def get_colide_ants(ant_list):
    colide_ant_list = []
    sorted(ant_list, key=lambda ant: ant.pos)
    len_ant_list = len(ant_list)
    for i in range(len_ant_list-1):
        if ant_list[index].pos == ant_list[index+1].pos:
            colide_ant_list.append((ant_list[i], ant_list[i+1]))
            
    return colide_ant_list
    

class Ant:
    def __init__(self, pos, direction):
        self.pos = pos
        self.direction = direction

    def move():
        if direction == 1:
            self.pos += 1
        else:
            self.pos -= 1

        if self.pos >= L:
            self.pos = self.pos - L
        if self.pos < 0:
            self.pos += L + self.pos

    def change_direction():
        if direction == 1:
            direction = 2
        else:
            direction = 1