結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 hukinorin
|
| 提出日時 | 2025-07-26 16:59:46 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,894 ms / 2,000 ms |
| コード長 | 6,061 bytes |
| コンパイル時間 | 439 ms |
| コンパイル使用メモリ | 82,792 KB |
| 実行使用メモリ | 101,136 KB |
| スコア | 4,568,832,810 |
| 最終ジャッジ日時 | 2025-07-26 17:05:42 |
| 合計ジャッジ時間 | 98,864 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
from time import perf_counter
start_time = perf_counter()
from random import randrange, random
def move(cx, cy, nx, ny):
if cx < nx:
for _ in range(nx - cx):
print("D")
elif cx > nx:
for _ in range(cx - nx):
print("U")
if cy < ny:
for _ in range(ny - cy):
print("R")
elif cy > ny:
for _ in range(cy - ny):
print("L")
def distance_diff(root, c_i, c_j):
diff = 0
diff += abs(root[c_i][0] - root[c_i - 1][0]) + abs(root[c_i][1] - root[c_i - 1][1])
if c_i + 1 < len(root):
diff += abs(root[c_i][0] - root[c_i + 1][0]) + abs(root[c_i][1] - root[c_i + 1][1])
diff += abs(root[c_j][0] - root[c_j - 1][0]) + abs(root[c_j][1] - root[c_j - 1][1])
if c_j + 1 < len(root):
diff += abs(root[c_j][0] - root[c_j + 1][0]) + abs(root[c_j][1] - root[c_j + 1][1])
return diff
N, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
cx, cy = 0, 0
s = 0
for b in range(19, 17, -1):
nearest_d = 10 ** 4
n_x, n_y = -1, -1
for i in range(N):
for j in range(N):
if (A[i][j] >> b) & 1:
d = abs(i - cx) + abs(j - cy)
if d < nearest_d:
nearest_d = d
n_x, n_y = i, j
if nearest_d + 1 <= T:
move(cx, cy, n_x, n_y)
cx, cy = n_x, n_y
T -= nearest_d + 1
s ^= A[cx][cy]
print("C")
root = [(cx, cy)]
for i in range(N):
for j in range(N):
if ((A[i][j] >> b) & 1) == 0:
root.append((i, j))
if b == 19:
root.append((cx, cy))
len_root = len(root)
distance = 0
for i in range(1, len_root):
distance += abs(root[i][0] - root[i - 1][0]) + abs(root[i][1] - root[i - 1][1])
if len_root > 2:
time_limit = (b + 1) * 1.85 / 20
while perf_counter() - start_time < time_limit:
c_i, c_j = randrange(1, len_root - 1), randrange(1, len_root - 1)
if c_i == c_j:
continue
new_distance = distance - distance_diff(root, c_i, c_j)
root[c_i], root[c_j] = root[c_j], root[c_i]
new_distance += distance_diff(root, c_i, c_j)
if new_distance < distance:
distance = new_distance
else:
root[c_i], root[c_j] = root[c_j], root[c_i]
for i in range(len_root - 2):
distance = abs(root[i][0] - root[i + 1][0]) + abs(root[i][1] - root[i + 1][1])
if distance + 1 <= T:
move(root[i][0], root[i][1], root[i + 1][0], root[i + 1][1])
cx, cy = root[i + 1]
T -= distance + 1
print("W")
A[cx][cy] ^= s
else:
break
else:
distance = abs(root[-1][0] - cx) + abs(root[-1][1] - cy)
if distance + 1 <= T:
move(cx, cy, root[-1][0], root[-1][1])
cx, cy = root[-1]
T -= distance + 1
print("C")
s ^= A[cx][cy]
else:
break
else:
if len(root) > 1:
root.append(root[1])
root.append((cx, cy))
len_root = len(root)
distance = 0
for i in range(1, len_root):
distance += abs(root[i][0] - root[i - 1][0]) + abs(root[i][1] - root[i - 1][1])
if len_root > 4:
time_limit = (b + 1) * 1.85 / 20
while perf_counter() - start_time < time_limit:
c_i, c_j = randrange(1, len_root - 2), randrange(1, len_root - 2)
if c_i == c_j:
continue
new_distance = distance - distance_diff(root, c_i, c_j)
root[c_i], root[c_j] = root[c_j], root[c_i]
new_distance += distance_diff(root, c_i, c_j)
if new_distance < distance:
distance = new_distance
else:
root[c_i], root[c_j] = root[c_j], root[c_i]
for i in range(len_root - 3):
distance = abs(root[i][0] - root[i + 1][0]) + abs(root[i][1] - root[i + 1][1])
if distance <= T:
move(root[i][0], root[i][1], root[i + 1][0], root[i + 1][1])
cx, cy = root[i + 1]
T -= distance
else:
break
if T > 0:
T -= 1
if i == 0:
print("C")
s ^= A[cx][cy]
else:
print("W")
A[cx][cy] ^= s
else:
break
else:
distance = abs(root[-2][0] - cx) + abs(root[-2][1] - cy)
if distance + 1 <= T:
move(cx, cy, root[-2][0], root[-2][1])
cx, cy = root[-2]
T -= distance + 1
print("C")
s ^= A[cx][cy]
else:
break
distance = abs(root[-1][0] - cx) + abs(root[-1][1] - cy)
if distance + 1 <= T:
move(cx, cy, root[-1][0], root[-1][1])
cx, cy = root[-1]
T -= distance + 1
print("C")
s ^= A[cx][cy]
else:
break