結果

問題 No.1421 国勢調査 (Hard)
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-20 14:18:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 2,534 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 79,564 KB
最終ジャッジ日時 2024-09-18 14:04:49
合計ジャッジ時間 4,842 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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

from typing import List, Optional
def solve_linear_equation_F2_col(A: List[int], b: List[int], m: int) -> Optional[List[int]]:
"""使线Ax = b
A ,.
b,.
"""
assert len(A) == len(b)
row = len(A)
for r in range(row):
indexes = max(range(r, row), key=lambda x: A[x])
if A[indexes] == 0:
rank = r
break
if indexes != r:
A[r], A[indexes] = A[indexes], A[r]
b[r], b[indexes] = b[indexes], b[r]
for j in range(row):
if r != j and A[j] > A[j] ^ A[r]:
A[j] ^= A[r]
b[j] ^= b[r]
else:
rank = row
# brank0None
if any(b[i] for i in range(rank, row)):
return
res = [0] * m
for r in range(rank):
res[A[r].bit_length() - 1] = b[r]
return res
if __name__ == "__main__":
# https://yukicoder.me/problems/no/1421
# n1ni1≤i≤nai
#
# m 访j1≤j≤mp
# Sjj
# !pSj
# !pXOR
# !mai
#
# mai
# -1
n, m = map(int, input().split())
A = [0] * m
b = [0] * m
for i in range(m):
_ = int(input())
houses = list(map(int, input().split()))
xor_ = int(input())
for house in houses:
A[i] |= 1 << (house - 1)
b[i] = xor_
res = solve_linear_equation_F2_col(A, b, n)
if res is None:
print(-1)
else:
print(*res, sep="\n")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0