Submission #3040686

---

Source Code Expand

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

N, L, T = map(int, raw_input().split())
T %= L

X1 = []
X2 = []
Xs = []
m = {}

for i in range(N):
    X, W = map(int, raw_input().split())
    if W == 1:
        X1.append(X)
    else:
        X2.append(X)
    m[X] = 0
    Xs.append((X, W))
if len(X1) != 0 and len(X2) != 0:
    for loop in range(2):
        pos1 = 0
        pos2 = 0
        bias = 0
        sz = len(X2)
        X2 = [X2[-1] - L] + X2 + [X2[0] + L]
        for x in X1:
            while True:
                if X2[pos1 + 1] + bias - x <= 2 * T:
                    pos1 += 1
                else:
                    break
                if pos1 > sz:
                    bias += L
                    pos1 = 1
            while True:
                if X2[pos2 + 1] < x:
                    pos2 += 1
                else:
                    break
            #print x, pos1, pos2, bias
            if loop == 0:
                m[x] = pos1 - pos2 + bias / L * sz
            else:
                m[(L - x) * (x != 0)] = pos1 - pos2 + bias / L * sz
        X2 = X2[1:-1]
        for i in range(len(X1)):
            X1[i] = (L - X1[i]) * (X1[i] != 0)
        for i in range(len(X2)):
            X2[i] = (L - X2[i]) * (X2[i] != 0)
        X1, X2 = sorted(X2), sorted(X1)

ans = [0] * N
for i in range(N):
    X, W = Xs[i]
    if W == 1:
        ans[(i + m[X]) % N] = (X + T) % L
    else:
        ans[(i - m[X]) % N] = (X - T) % L

for i in range(N):
    print ans[i]

Submission Info

Judge Result