結果

問題 No.5022 XOR Printer
ユーザー kazari4
提出日時 2025-07-26 16:59:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 2,105 bytes
コンパイル時間 495 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 64,404 KB
スコア 4,588,555,925
最終ジャッジ日時 2025-07-26 17:02:09
合計ジャッジ時間 5,302 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

sys.setrecursionlimit(1 << 25)
N, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
total_ans = []
ci, cj = 0, 0
s = 0


def build_basis():
    basis = []
    for i in range(N):
        for j in range(N):
            x = A[i][j]
            v = x
            for b, _, _ in basis:
                v = min(v, v ^ b)
            if v:
                basis.append((x, i, j))
                basis.sort(key=lambda t: -t[0].bit_length())
    return basis


def move_to(ti, tj):
    global ci, cj
    ops = []
    while ci < ti:
        ops.append("D")
        ci += 1
    while ci > ti:
        ops.append("U")
        ci -= 1
    while cj < tj:
        ops.append("R")
        cj += 1
    while cj > tj:
        ops.append("L")
        cj -= 1
    return ops


def pick_for_bit(target_bit, s, basis):
    picks = []
    cur = s
    for b, i, j in basis:
        if ((cur ^ b) >> (target_bit + 1)) == 0 and ((cur ^ b) >> target_bit) & 1:
            cur ^= b
            picks.append((i, j))
        if (cur >> (target_bit + 1)) == 0 and ((cur >> target_bit) & 1):
            break
    return picks, cur


def apply_picks(picks):
    global s
    ops = []
    for i, j in picks:
        ops += move_to(i, j)
        ops.append("C")
        s ^= A[i][j]
    return ops


def apply_bitwise_writing(target_bit):
    global s
    ops = []
    for i in range(N):
        direction = 1 if i % 2 == 0 else -1
        for j in range(N)[::direction]:
            ops += move_to(i, j)
            if ((A[i][j] ^ s) >> target_bit) & 1 and (A[i][j] ^ s) > A[i][j]:
                ops.append("W")
                A[i][j] ^= s
    return ops


def bit_length(x):
    return x.bit_length()


basis = build_basis()

bit = 19
while bit >= 0:
    if len(total_ans) >= T:
        break

    picks, new_s = pick_for_bit(bit, s, basis)
    pick_ops = apply_picks(picks)
    write_ops = apply_bitwise_writing(bit)

    if len(total_ans) + len(pick_ops) + len(write_ops) > T:
        break

    total_ans += pick_ops + write_ops
    bit -= 1

for op in total_ans[:T]:
    print(op)
0