結果

問題 No.3602 Queen XOR Score
コンテスト
ユーザー gomaazarasi
提出日時 2026-07-12 12:55:15
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 3,419 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 244 ms
コンパイル使用メモリ 96,236 KB
実行使用メモリ 118,180 KB
最終ジャッジ日時 2026-07-24 20:37:55
合計ジャッジ時間 24,060 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from copy import deepcopy

def Gaussian_Elimination(equation, mod):
    
    equation_num = len(equation)
    variable_num = len(equation[0])-1
    ans = [0 for i in range(variable_num)]
    every = [-1 for i in range(variable_num)]
    answer = True
    
    for i in range(equation_num):
        for j in range(len(equation[i])):
            equation[i][j] %= mod
    
    s = set([i for i in range(equation_num)])
    order = []
    
    for i in range(variable_num):
        index = -1
        inv = 0
        for j in s:
            if equation[j][i] == 0:
                continue
            if index == -1:
                index = j
                inv = pow(equation[j][i],-1,mod)
                for k in range(i,variable_num+1):
                    equation[j][k] *= inv
                    equation[j][k] %= mod
            else:
                x = equation[j][i] * inv
                x %= mod
                for k in range(i,variable_num+1):
                    equation[j][k] -= equation[index][k]*x
                    equation[j][k] %= mod
        if index == -1:
            every[i] = 1
        else:
            order.append(index)
            s.discard(index)
    
    for i in s:
        add = 0
        for j in equation[i]:
            add += j
        if add != 0:
            answer = False
            break
    
    if answer == False:
        for i in range(variable_num):
            every[i] = -1
        return ans,every
    
    for i in range(len(order)-1,-1,-1):
        val = equation[order[i]][-1]
        flag = 0
        for j in range(variable_num-1,-1,-1):
            if every[j] != -1:
                val -= equation[order[i]][j]*ans[j]
                val %= mod
                if every[j] == 1:
                    flag = 1
            else:
                ans[j] = val
                every[j] = flag
                break
    
    return ans,every


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

q = int(input())

equation = [[] for i in range(60)]

for i in range(60):
    for j in range(h):
        for k in range(w):
            if a[j][k]&(1<<i):
                equation[i].append(1)
            else:
                equation[i].append(0)
    equation[i].append(0)

for _ in range(q):
    x = int(input())
    XX = x
    
    if x == 0:
        print(3)
        print(1,1)
        print(1,2)
        print(1,1)
        print(1,2)
        continue
    
    for i in range(60):
        if x&(1<<i):
            equation[i][hw] = 1
        else:
            equation[i][hw] = 0
    
    answer,every = Gaussian_Elimination(deepcopy(equation),2)
    
    if every[0] == -1:
        print(-1)
        continue
    
    order = [set() for i in range(h)]
    
    for i in range(h):
        for u in range(w):
            index = i*w+u
            
            if answer[index] == 1:
                order[i].add((i,u))
    ans = []
    
    y,x = 0,0
    
    for i in range(h):
        if len(order[i]) == 0:
            continue
        y,x = i,x
        ans.append((y+1,x+1))
        
        flag = (y,x) in order[i]
        order[i].discard((y,x))
        
        for Y,X in order[i]:
            if flag:
                y,x = Y,X
            ans.append((Y+1,X+1))
        
        if flag == False:
            ans.append((y+1,x+1))
    
    print(len(ans)-1)
    for y,x in ans:
        print(y,x)
0