結果

問題 No.5022 XOR Printer
ユーザー Kiri8128
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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()
0