結果

問題 No.2274 三角彩色
ユーザー ecotteaecottea
提出日時 2023-03-01 01:52:50
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,377 ms / 2,000 ms
コード長 2,586 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2024-09-16 02:59:05
合計ジャッジ時間 7,397 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
11,008 KB
testcase_01 AC 32 ms
10,880 KB
testcase_02 AC 32 ms
11,008 KB
testcase_03 AC 32 ms
10,880 KB
testcase_04 AC 32 ms
10,880 KB
testcase_05 AC 32 ms
11,008 KB
testcase_06 AC 32 ms
10,880 KB
testcase_07 AC 32 ms
10,880 KB
testcase_08 AC 32 ms
11,008 KB
testcase_09 AC 33 ms
10,880 KB
testcase_10 AC 33 ms
11,008 KB
testcase_11 AC 34 ms
10,880 KB
testcase_12 AC 35 ms
11,008 KB
testcase_13 AC 48 ms
11,008 KB
testcase_14 AC 55 ms
11,264 KB
testcase_15 AC 645 ms
16,768 KB
testcase_16 AC 628 ms
16,640 KB
testcase_17 AC 619 ms
16,768 KB
testcase_18 AC 1,327 ms
16,640 KB
testcase_19 AC 1,377 ms
16,512 KB
testcase_20 AC 1,260 ms
16,640 KB
testcase_21 AC 72 ms
12,032 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import re
import sys
import bisect

dump = lambda *x : print(*x, file = sys.stderr)

def coordinate_compression(a):
    n = len(a)
    x = sorted(list(set(a)))
    b = [0] * n
    for i in range(n):
        b[i] = bisect.bisect_left(x, a[i])
    return b

def bit_matrix_rank(a):
    n, m = len(a), len(a[0])

    i, j = 0, 0

    while i < n and j < m:
        i2 = i
        while i2 < n and not a[i2][j]:
            i2 += 1
        
        if i2 == n:
            j += 1
            continue

        a[i], a[i2] = a[i2], a[i]

        for i2 in range(n):
            if i2 == i:
                continue

            if a[i2][j]:
                for j2 in range(m):
                    a[i2][j2] ^= a[i][j2]
        
        i += 1
        j += 1
    
    return i


content = input()
pattern = r'^(\d+) (\d+) (\d+) (\d+)$'
result = re.match(pattern, content)

if not result:
    sys.exit("format error.")

N, M, B, Q = map(int, result.groups())

if not (3 <= N and N <= 10**18):
    sys.exit("N")
if not (3 <= M and M <= 4*(10**2)):
    sys.exit("M")
if not (2 <= B and B <= 10**9):
    sys.exit("L")
if not (1 <= Q and Q <= 10**3):
    sys.exit("Q")

ijs = []

for _ in range(M):
    content = input()
    pattern = r'^(\d+) (\d+)$'
    result = re.match(pattern, content)

    if not result:
        sys.exit("format error.")

    i, j = map(int, result.groups())

    if not (0 <= i and i < j and j < N):
        sys.exit("i j")

    ijs += [i, j]
dump(ijs)

ijs_cp = coordinate_compression(ijs)
h = max(ijs_cp) + 1
dump(ijs_cp)
dump(h)

ms = []

for _ in range(Q):
    content = input()
    pattern = r'^(\d+) (\d+) (\d+)$'
    result = re.match(pattern, content)

    if not result:
        sys.exit("format error.")

    m0, m1, m2 = map(int, result.groups())

    if not (0 <= m0 and m0 < m1 and m1 < m2 and m2 < M):
        sys.exit("m0 m1 m2")

    vs = []
    vs += ijs[2 * m0 : 2 * m0 + 2]
    vs += ijs[2 * m1 : 2 * m1 + 2]
    vs += ijs[2 * m2 : 2 * m2 + 2]
    vs.sort()

    if not (vs[0] == vs[1] and vs[1] != vs[2] and vs[2] == vs[3] and vs[3] != vs[4] and vs[4] == vs[5]):
        sys.exit("m0 m1 m2 loop")

    ms += [[m0, m1, m2]]
dump(ms)

mat = [[0 for j in range(M)] for i in range(h)]
for m in range(M):
    for t in range(2):
        mat[ijs_cp[2 * m + t]][m] = 1
dump(mat)

mat2 = [[0 for j in range(M)] for i in range(Q)]
for q in range(Q):
    for t in range(3):
        mat2[q][ms[q][t]] = 1
dump(mat2)

r = bit_matrix_rank(mat)
r2 = bit_matrix_rank(mat2)
dump(r, r2)

resT = pow(2, r2, B)
resS = (pow(2, M - r, B) - resT + B) % B

print(resS, resT)
0