結果

問題 No.2505 matriX cOnstRuction
ユーザー suisen
提出日時 2023-02-21 12:36:34
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,372 bytes
コンパイル時間 467 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 319,720 KB
最終ジャッジ日時 2024-09-15 18:48:33
合計ジャッジ時間 30,941 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 63
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from itertools import product
import sys
from typing import List, Tuple
def floor_pow2(n: int):
    x = 1
    while (x << 1) <= n:
        x <<= 1
    return x
class Node:
    def __init__(self) -> None:
        self.lch = None
        self.rch = None
        self.weight = 0
    
    def left_child_or_create(self) -> 'Node':
        if self.lch is None:
            self.lch = Node()
        return self.lch
    def right_child_or_create(self) -> 'Node':
        if self.rch is None:
            self.rch = Node()
        return self.rch
L = 30
inf = 1 << 30
def solve(n: int, m: int, R: List[int], C: List[int], A: List[List[int]]):
    for i, j in product(range(n), range(m)):
        if A[0][0] ^ A[0][j] ^ A[i][0] ^ A[i][j]:
            print(-1)
            return
        
    root = Node()
    # f(X) += W * [X ^ Y > Z]
    def add_weight(Y: int, Z: int, W: int):
        YZ = Y ^ Z
        cur = root
        for bit in reversed(range(L)):
            if (YZ >> bit) & 1:
                if not ((Z >> bit) & 1):
                    cur.left_child_or_create().weight += W
                cur = cur.right_child_or_create()
            else:
                if not ((Z >> bit) & 1):
                    cur.right_child_or_create().weight += W
                cur = cur.left_child_or_create()
    for i in range(n):
        Y = A[0][0] ^ A[i][0]
        if R[i]:
            add_weight(Y, 0, 1)
            add_weight(Y, R[i], 1)
            add_weight(Y, 2 * floor_pow2(R[i]) - 1, inf)
        else:
            add_weight(Y, 0, inf)
    for j in range(m):
        Y = A[0][j]
        if C[j]:
            add_weight(Y, 0, 1)
            add_weight(Y, C[j], 1)
            add_weight(Y, 2 * floor_pow2(C[j]) - 1, inf)
        else:
            add_weight(Y, 0, inf)
    min_weight = (inf, -1)
    
    st : List[Tuple[Node, int, int]] = [(root, 0, 1 << L)]
    while st:
        node, l, r = st.pop()
        weight = node.weight
        if r - l == 1:
            min_weight = min(min_weight, (weight, l))
            continue
        mid = (l + r) >> 1
        if node.lch is None:
            min_weight = min(min_weight, (weight, mid - 1))
        else:
            node.lch.weight += weight
            st.append((node.lch, l, mid))
        if node.rch is None:
            min_weight = min(min_weight, (weight, r - 1))
        else:
            node.rch.weight += weight
            st.append((node.rch, mid, r))
    
    cost, X = min_weight
    if cost >= inf:
        print(-1)
        return
    print(cost, end='\r\n')
    for j in range(m):
        t = X ^ A[0][j]
        if t == 0:
            continue
        elif t <= C[j]:
            print('c', j + 1, t, end='\r\n')
        else:
            print('c', j + 1, t ^ C[j], end='\r\n')
            print('c', j + 1, C[j], end='\r\n')
    for i in range(n):
        s = X ^ A[0][0] ^ A[i][0]
        if s == 0:
            continue
        elif s <= R[i]:
            print('r', i + 1, s, end='\r\n')
        else:
            print('r', i + 1, s ^ R[i], end='\r\n')
            print('r', i + 1, R[i], end='\r\n')
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    R = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A = [list(map(int, input().split())) for _ in range(n)]
    solve(n, m, R, C, A)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0