結果

問題 No.3602 Queen XOR Score
コンテスト
ユーザー gomaazarasi
提出日時 2026-07-22 19:49:55
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 179 ms / 2,000 ms
+ 441µs
コード長 2,415 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 247 ms
コンパイル使用メモリ 96,240 KB
実行使用メモリ 88,056 KB
最終ジャッジ日時 2026-07-24 20:37:56
合計ジャッジ時間 5,773 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 


h,w = list(map(int,input().split()))
hw = h*w
a = [list(map(int,input().split())) for i in range(h)]

q = int(input())
query = [int(input()) for i in range(q)]

x = []


for bit in range(60):
    y = []
    for i in range(h):
        for u in range(w):
            if a[i][u]&(1<<bit):
                y.append(1)
            else:
                y.append(0)
    for i in range(q):
        if query[i]&(1<<bit):
            y.append(1)
        else:
            y.append(0)
    
    x.append(y)

out = [[-1 for i in range(q)] for i in range(hw)]
remain = set([i for i in range(60)])
order = []

for i in range(hw):
    index = -1
    for u in remain:
        if index == -1:
            if x[u][i] == 1:
                index = u
        else:
            if x[u][i] == 1:
                for k in range(i,len(x[u])):
                    x[u][k] ^= x[index][k]
    
    if index == -1:
        for u in range(q):
            out[i][u] = 0
    
    else:
        order.append(index)
        remain.discard(index)


for i in remain:
    for u in range(hw,hw+q):
        if x[i][u]:
            query[u-hw] = -1


for i in range(len(order)-1,-1,-1):
    for u in range(hw-1,-1,-1):
        if x[order[i]][u]:
            if out[u][0] == -1:
                for k in range(hw,hw+q):
                    out[u][k-hw] = x[order[i]][k]
                break
            elif out[u][0] != -1:
                for k in range(hw,hw+q):
                    x[order[i]][k] ^= out[u][k-hw]

for _ in range(q):
    if query[_] == -1:
        print(-1)
        continue
    
    if query[_] == 0:
        print(3)
        print(1,1)
        print(1,2)
        print(1,1)
        print(1,2)
        continue
    
    z = [set() for i in range(w)]
    ans = []
    
    for i in range(h):
        for u in range(w):
            index = i*w+u
            if out[index][_]:
                z[u].add(i)
    
    Y,X = 0,0
    
    for i in range(w):
        sy = Y
        if len(z[i]) == 0:
            continue
        X = i
        flag = bool(Y in z[i])
        z[i].discard(Y)
        ans.append((Y+1,X+1))
        
        while len(z[i]):
            Y = z[i].pop()
            ans.append((Y+1,X+1))
        
        if flag:
            continue
        
        else:
            Y = sy
            ans.append((Y+1,X+1))
    
    cc = 0
    print(len(ans)-1)
    for Y,X in ans:
        print(Y,X)
        cc ^= a[Y-1][X-1]
0