結果
問題 |
No.5022 XOR Printer
|
ユーザー |
![]() |
提出日時 | 2025-07-26 15:39:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 5,992 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 82,568 KB |
実行使用メモリ | 75,084 KB |
スコア | 5,101,148,101 |
最終ジャッジ日時 | 2025-07-26 15:39:44 |
合計ジャッジ時間 | 6,755 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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): for j in range(self.N): II = [] for di in (-1, 1): for dj in (-1, 1): if i <= self.N - 2 and j 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) if i >= self.N - 2: 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) 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) ma = -1 mak = None maI = None maM = None for I in II: ng = 0 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): # 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()