Submission #3040862
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()) X1 = [] X2 = [] Xs = [] m = {} mL = {} mul = T_ / L 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 mL[X] = 0 Xs.append((X, W)) T = L 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 if loop == 0: mL[x] = pos1 - pos2 + bias / L * sz else: mL[(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) T = T_ % L 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 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) #print m ans = [0] * N for i in range(N): X, W = Xs[i] if W == 1: ans[(i + m[X] + mL[X] * mul) % N] = (X + T) % L else: ans[(i - m[X] - mL[X] * mul) % N] = (X - T) % L for i in range(N): print ans[i]
Submission Info
Submission Time | |
---|---|
Task | C - Ants on a Circle |
User | monolith |
Language | Python (2.7.6) |
Score | 700 |
Code Size | 2690 Byte |
Status | AC |
Exec Time | 859 ms |
Memory | 40784 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 14 ms | 3064 KB |
sample_02.txt | AC | 12 ms | 2944 KB |
subtask_1_01.txt | AC | 501 ms | 24460 KB |
subtask_1_02.txt | AC | 390 ms | 21476 KB |
subtask_1_03.txt | AC | 859 ms | 40784 KB |
subtask_1_04.txt | AC | 812 ms | 40656 KB |
subtask_1_05.txt | AC | 134 ms | 8432 KB |
subtask_1_06.txt | AC | 190 ms | 14892 KB |
subtask_1_07.txt | AC | 769 ms | 40400 KB |
subtask_1_08.txt | AC | 772 ms | 40400 KB |
subtask_1_09.txt | AC | 502 ms | 25576 KB |
subtask_1_10.txt | AC | 430 ms | 23340 KB |
subtask_1_11.txt | AC | 63 ms | 6768 KB |
subtask_1_12.txt | AC | 362 ms | 32228 KB |
subtask_1_13.txt | AC | 502 ms | 24168 KB |
subtask_1_14.txt | AC | 454 ms | 22928 KB |
subtask_1_15.txt | AC | 12 ms | 2944 KB |
subtask_1_16.txt | AC | 12 ms | 2944 KB |