#840023 (PyPy3) No.2505 matriX cOnstRuction

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX