結果

問題 No.3602 Queen XOR Score
コンテスト
ユーザー kidodesu
提出日時 2026-07-24 23:04:15
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 138 ms / 2,000 ms
+ 713µs
コード長 1,736 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 232 ms
コンパイル使用メモリ 95,980 KB
実行使用メモリ 85,560 KB
最終ジャッジ日時 2026-07-24 23:04:21
合計ジャッジ時間 5,978 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    h, w = list(map(int, input().split()))
    A = [list(map(int, input().split())) for _ in range(h)]
    I = [i for i in range(h*w)]
    I.sort(key = lambda xy: -A[xy//w][xy%w])
    Base = []
    for y in range(h):
        for x in range(w):
            a = A[y][x]
            s = 1 << (y*w+x)
            for b, t in Base:
                if a^b < a:
                    a = a^b
                    s ^= t
            if a:
                Base.append((a, s))
    Base.sort(reverse = True)
    for _ in range(int(input())):
        X = int(input())
        B = [[0 for _ in range(w)] for _ in range(h)]
        s = 0
        for b, t in Base:
            if X^b < X:
                X ^= b
                s ^= t
        if X:
            print(-1)
            continue
        if s == 0:
            print(3)
            print(1, 1)
            print(1, 2)
            print(1, 1)
            print(1, 2)
            continue
        for y in range(h):
            for x in range(w):
                if s >> (y*w+x) & 1:
                    B[y][x] = 1
        Ans = [(0, 0)]
        for y in range(h):
            if sum(B[y][1:]):
                if y:
                    Ans.append((y, 0))
                for x in range(1, w):
                    if B[y][x]:
                        Ans.append((y, x))
                Ans.append((y, 0))
        if Ans[-1] != (0, 0):
            Ans.append((0, 0))
        f = 0
        for y in range(1, h):
            f = 1
            if B[y][0]:
                Ans.append((y, 0))
        for y, x in Ans:
            B[y][x] ^= 1
        if B[0][0]:
            Ans = Ans[1:]
            
        print(len(Ans)-1)
        for y, x in Ans:
            print(y+1, x+1)

main()
0