結果
| 問題 |
No.5022 XOR Printer
|
| コンテスト | |
| ユーザー |
 Kiri8128
|
| 提出日時 | 2025-07-26 16:21:15 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 119 ms / 2,000 ms |
| コード長 | 6,719 bytes |
| コンパイル時間 | 214 ms |
| コンパイル使用メモリ | 82,556 KB |
| 実行使用メモリ | 77,592 KB |
| スコア | 5,163,847,597 |
| 最終ジャッジ日時 | 2025-07-26 16:22:36 |
| 合計ジャッジ時間 | 7,476 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
from random import randrange, random, seed as random_seed, shuffle, randint
from sys import stderr
from math import log, exp, sqrt, hypot
class Data:
def __init__(self, N, T, A):
self.N = N
self.T = T
self.A = A
self.ans = []
self.i = 0
self.j = 0
self.s = 0
self.t = 0
def __str__(self):
return f"N: {self.N}, A: {self.A}, I: {self.I}"
def calc_score(self):
score = 0
for a in self.A:
score += sum(a)
return score
# 入力方法はローカル用と提出用の2つ。どちらも使うので消さないこと
@classmethod
def preset_data(cls, seed):
# TODO
with open("input\\" + str(seed).zfill(4) + ".txt", "r") as tf:
input_ = lambda: tf.readline().rstrip()
# TODO: update
return cls(N, M, S)
@classmethod
def input_real(cls):
N, T = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(N)]
return cls(N, T, A)
@classmethod
def random_testcase(cls, seed):
N = 10
T = 1000
random_seed(seed)
A = [[randrange(2 ** 20) for _ in range(N)] for _ in range(N)]
return cls(N, T, A)
def show(self):
for a in self.A:
print(a)
def act(self, a):
if self.t >= self.T:
return
self.t += 1
self.ans.append(a)
if a == "U":
assert self.i
self.i -= 1
elif a == "D":
assert self.i < self.N - 1
self.i += 1
elif a == "L":
assert self.j
self.j -= 1
elif a == "R":
assert self.j < self.N - 1
self.j += 1
elif a == "C":
self.s ^= self.A[self.i][self.j]
elif a == "W":
self.A[self.i][self.j] ^= self.s
def move_to(self, ii, jj):
while self.i > ii:
self.act("U")
if self.t >= self.T: return
while self.i < ii:
self.act("D")
if self.t >= self.T: return
while self.j > jj:
self.act("L")
if self.t >= self.T: return
while self.j < jj:
self.act("R")
if self.t >= self.T: return
def solve_old(self):
k = 19
for k in range(19, 15, -1):
print("k =", k)
f = 0
while f == 0:
for i in range(self.N):
for j in range(self.N):
if 1 << k < (self.s ^ self.A[i][j]) < 1 << k + 1:
f = 1
break
if randrange(100) == 0:
self.act("C")
print("self.s =", self.s)
if f:
break
if not f:
break
self.move_to(i, j)
self.act("C")
print("s =", self.s)
for i in range(self.N):
for j in range(self.N):
if self.A[i][j] ^ self.s > self.A[i][j]:
self.move_to(i, j)
self.act("W")
if self.t >= self.T:
break
def solve(self):
for i in range(self.N):
dirj = 1 if i % 2 == 0 else -1
J = range(self.N) if dirj == 1 else range(self.N)[::-1]
if i == self.N - 1:
J = list(J[:self.N//2]) + sorted([j for j in J[self.N//2:]], key = lambda j: self.A[i][j])
for j in J:
II = []
for di in (-1, 1):
for dj in (-1, 1):
if i <= self.N - 2 and ((dirj > 0 and j and dj > 0) or (dirj < 0 and j < self.N - 1 and dj < 0)):
continue
I = [(i, j + dj), (i + di, j + dj), (i + di * 2, j + dj), (i + di * 2, j), (i + di, j), (i, j)]
II.append(I)
I = [(i, j + dj), (i, j + dj * 2), (i + di, j + dj * 2), (i + di, j + dj), (i + di, j), (i, j)]
II.append(I)
I = [(i + di, j + dj), (i + di, j), (i + di, j - dj), (i, j - dj), (i, j)]
II.append(I)
if i == self.N - 1: # and j >= self.N // 2:
I = [(i, j + dj), (i + di, j + dj), (i + di * 2, j + dj), (i + di * 3, j + dj), (i + di * 3, j), (i + di * 2, j), (i + di, j), (i, j)]
II.append(I)
I = [(i, j + dj), (i + di, j + dj), (i + di * 2, j + dj), (i + di * 3, j + dj), (i + di * 4, j + dj), (i + di * 4, j), (i + di * 3, j), (i + di * 2, j), (i + di, j), (i, j)]
II.append(I)
ma = -1
mak = None
maI = None
maM = None
for _I in II:
ng = 0
I = [(self.i, self.j)] + _I
# I = _I
for ii, jj in I:
if not (0 <= ii < self.N and 0 <= jj < self.N):
ng = 1
break
if ng:
continue
aa = [self.A[i][j] for i, j in I]
M = len(I)
for k in range(1 << M):
t = self.s ^ self.A[i][j]
for l in range(M):
if k >> l & 1 == 0:
continue
a = aa[l]
t ^= a
if t > ma:
ma = t
mak = k
maI = I
maM = M
assert maM is not None, (i, j)
k = mak
I = maI
M = maM
for l in range(M):
if k >> l & 1 == 0:
continue
ii, jj = I[l]
self.move_to(ii, jj)
self.act("C")
self.move_to(i, j)
self.act("W")
def answer(self):
if LOCAL:
print(len(self.ans))
if 1:
for a in self.ans:
print(a)
LOCAL = 0
if LOCAL:
data = Data.random_testcase(2)
print(data.calc_score())
data.show()
data.solve()
data.show()
data.answer()
print(data.calc_score())
else:
data = Data.input_real()
data.solve()
# data.show()
data.answer()