結果

問題 No.5022 XOR Printer
ユーザー ra5anchor
提出日時 2025-07-31 05:40:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 5,312 bytes
コンパイル時間 286 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 82,900 KB
スコア 5,153,665,019
最終ジャッジ日時 2025-07-31 05:40:17
合計ジャッジ時間 10,243 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import copy
import random
from time import perf_counter
import argparse
import sys
import math

MAX = 10**8

class TimeKeeper:
    def __init__(self):
        self.start_time = perf_counter()
    def is_time_over(self, LIMIT):
        return (perf_counter() - self.start_time) >= LIMIT
    def time_now(self):
        return (perf_counter() - self.start_time)



###########################################
def main(DEBUG):
    tk = TimeKeeper()
    if DEBUG == True:
        LIMIT = 0.3
    else:
        LIMIT = 1.7

    def cal_score(A):
        N = 10
        score = 0
        for i in range(N):
            for j in range(N):
                score += A[i][j]
        return score

    def cal_score_sim(ANS):
        N = 10
        nowi = 0
        nowj = 0
        s = 0
        B = [[0]*N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                B[i][j] = A[i][j]
        if len(ANS) > 1000:
            return -1
        for c in ANS:
            if c == "L":
                nowj -= 1
            elif c == "R":
                nowj += 1
            elif c == "U":
                nowi -= 1
            elif c == "D":
                nowi += 1
            elif c == "W":
                B[nowi][nowj] ^= s
            elif c == "C":
                s ^= B[nowi][nowj]
            if nowi < 0 or nowi >= N or nowj < 0 or nowj >= N:
                return -1
        score = 0
        for i in range(N):
            for j in range(N):
                score += B[i][j]
        return score

    def goto(nowi, nowj, toi, toj):
        res = []
        di = toi - nowi
        dj = toj - nowj
        if di > 0:
            for _ in range(di):
                res.append("D")
        else:
            for _ in range(abs(di)):
                res.append("U")
        if dj > 0:
            for _ in range(dj):
                res.append("R")
        else:
            for _ in range(abs(dj)):
                res.append("L")
        return res
       
    def get_order(w_pos, nowi, nowj):
        # greedy
        w = []
        while len(w_pos)>0:
            w_pos.sort(key=lambda x: -abs(x[0]-nowi)-abs(x[1]-nowj))
            (toi, toj) = w_pos.pop()
            w.append((toi, toj))
            nowi = toi
            nowj = toj
        return w            


    def solve():
        X = [[0]*N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                X[i][j] = A[i][j]
        nowi = 0
        nowj = 0
        s = 0
        actions = []
        
        for k in range(20): # k:keta
            # sを設定する
            xnow = s >> 20-1-k & 1
            kouho = []
            for i in range(N):
                for j in range(N):
                    # if (X[i][j] >> (20-1-k)) & 1 == 1:
                    if (X[i][j] >> 20-1-k+1 == (1 << k) - 1) and (X[i][j] >> 20-1-k & 1 == 1-xnow):
                        ti, tj = i, j
                        d = abs(nowi-i) + abs(nowj-j)
                        kouho.append((d, ti, tj))
            kouho.sort()
            if len(kouho)==0:
                print(f"not found kouho {k=} -> break", file=sys.stderr)
                break
            d, ti, tj = kouho[0]

            # 目的地へ向かう
            res = goto(nowi, nowj, ti, tj)
            actions.extend(res)
            nowi = ti
            nowj = tj

            # Copyして完成
            actions.append("C")
            s ^= X[nowi][nowj]
            
            # 書き込みする地点列挙
            w_pos = []
            for i in range(N):
                for j in range(N):
                    # if (X[i][j] >> (20-1-k)) & 1 == 0:
                    if (X[i][j] >> 20-1-k+1 == (1 << k) - 1) and (X[i][j] >> 20-1-k & 1 == 0):
                        w_pos.append((i, j))
            
            if len(w_pos) == 0:
                print(f"not found w_pos {k=} -> break", file=sys.stderr)
                break
            # 巡回する順番決め
            w_pos_ordered = get_order(w_pos, nowi, nowj)
            # 一つ残して巡回
            for (toi, toj) in w_pos_ordered[:-1]:
                res = goto(nowi, nowj, toi, toj)
                actions.extend(res)
                nowi = toi
                nowj = toj
                # Print
                actions.append("W")
                X[nowi][nowj] ^= s

            # 最後の一つはsに書き込む
            toi, toj = w_pos_ordered[-1]
            res = goto(nowi, nowj, toi, toj)
            actions.extend(res)
            nowi = toi
            nowj = toj
            # Copy
            actions.append("C")
            s ^= X[nowi][nowj]
                
            print(f"{k=} {s=} {bin(s)=}", file=sys.stderr)
            print(X, file=sys.stderr)
        return actions

    N, T = map(int, input().split())
    # N=10, T=1000
    A = [list(map(int, input().split())) for _ in range(N)]

    ANS = solve()

    print(f"T: {len(ANS)}", file=sys.stderr)
    ANS = ANS[:T]
    sc = cal_score_sim(ANS)

    print(f"SC: {sc}", file=sys.stderr)
    print(*ANS, sep='\n')


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Debug mode')
    parser.add_argument('--debug', action='store_true', help='Enable debug mode')
    args = parser.parse_args()
    main(args.debug)
0