結果

問題 No.1421 国勢調査 (Hard)
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-20 14:18:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 2,534 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 81,936 KB
実行使用メモリ 78,888 KB
最終ジャッジ日時 2023-10-18 18:06:06
合計ジャッジ時間 4,670 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
66,316 KB
testcase_01 AC 62 ms
66,300 KB
testcase_02 AC 63 ms
66,840 KB
testcase_03 AC 67 ms
66,844 KB
testcase_04 AC 73 ms
66,864 KB
testcase_05 AC 63 ms
66,844 KB
testcase_06 AC 64 ms
66,852 KB
testcase_07 AC 65 ms
66,848 KB
testcase_08 AC 65 ms
66,852 KB
testcase_09 AC 64 ms
66,848 KB
testcase_10 AC 63 ms
66,852 KB
testcase_11 AC 63 ms
66,852 KB
testcase_12 AC 62 ms
66,644 KB
testcase_13 AC 61 ms
66,644 KB
testcase_14 AC 62 ms
66,660 KB
testcase_15 AC 61 ms
66,644 KB
testcase_16 AC 62 ms
66,684 KB
testcase_17 AC 61 ms
66,680 KB
testcase_18 AC 61 ms
66,680 KB
testcase_19 AC 63 ms
66,640 KB
testcase_20 AC 62 ms
66,712 KB
testcase_21 AC 63 ms
66,692 KB
testcase_22 AC 139 ms
78,840 KB
testcase_23 AC 140 ms
78,888 KB
testcase_24 AC 138 ms
78,884 KB
testcase_25 AC 139 ms
78,888 KB
testcase_26 AC 138 ms
78,880 KB
testcase_27 AC 139 ms
78,884 KB
testcase_28 AC 138 ms
78,876 KB
testcase_29 AC 138 ms
78,880 KB
testcase_30 AC 138 ms
78,884 KB
testcase_31 AC 137 ms
78,880 KB
権限があれば一括ダウンロードができます

ソースコード

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

    # 向量b在rank位置之后的所有元素是否为0。如果不是，返回None，表示方程无解。
    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
    # 在一个国家里有n个城镇，它们分别被编号为1到n。在编号为i（1≤i≤n）的城镇中有ai栋房子，
    # 现在只知道这个情况。这个国家的国王想知道每个城镇分别有多少栋房子。
    # 有一天，m 个旅行者访问了这个国家。第j（1≤j≤m）个旅行者游览了国王的p个城镇，
    # 这些城镇的编号为Sj。每个旅行者j在离开国王时报告了以下两点：
    # !他们参观过的城市数量p，以及这些城市的编号Sj。
    # !他们参观过的p个城市中，房子数量的总XOR值。
    # !于是，国王决定根据m个旅行者的报告计算出每个城市的房子数量ai。
    # 但是，旅行者中可能有人提交了虚假的报告。
    # 如果存在一个与m个旅行者的所有报告相符的ai值组合，请输出其中的一个。
    # 如果没有（旅行者的报告中存在矛盾），请输出-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")
0