結果

問題 No.2505 matriX cOnstRuction
コンテスト
ユーザー suisen
提出日時 2023-02-14 20:23:41
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,368 bytes
コンパイル時間 683 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 248,288 KB
最終ジャッジ日時 2024-09-15 18:41:39
合計ジャッジ時間 28,444 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import product
import sys
from time import perf_counter
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 = 60

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:
                nxt = cur.right_child_or_create()
            else:
                nxt = cur.left_child_or_create()
            if not ((Z >> bit) & 1):
                cur.weight += W
                nxt.weight -= W
            cur = nxt

    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)

    beg = perf_counter()

    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, l))
        else:
            node.lch.weight += weight
            st.append((node.lch, l, mid))

        if node.rch is None:
            min_weight = min(min_weight, (weight, mid))
        else:
            node.rch.weight += weight
            st.append((node.rch, mid, r))
    
    print((perf_counter() - beg), file=sys.stderr)
    
    cost, X = min_weight

    if cost >= inf:
        print(-1)
        return

    print(cost)
    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)
        else:
            p = floor_pow2(R[i])
            print('r', i + 1, p)
            print('r', i + 1, s ^ p)
    for j in range(m):
        t = X ^ A[0][j]
        if t == 0:
            continue
        elif t <= C[j]:
            print('c', j + 1, t)
        else:
            p = floor_pow2(C[j])
            print('c', j + 1, p)
            print('c', j + 1, t ^ p)

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)
0