結果

問題 No.2274 三角彩色
ユーザー ecotteaecottea
提出日時 2023-03-01 01:42:56
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 2,141 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 11,184 KB
実行使用メモリ 40,704 KB
最終ジャッジ日時 2023-10-14 07:41:58
合計ジャッジ時間 5,314 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import re
import sys
import bisect
import numpy as np

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

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 = np.zeros((h, M))
for m in range(M):
    for t in range(2):
        mat[ijs_cp[2 * m + t]][m] = 1
dump(mat)

mat2 = np.zeros((Q, M))
for q in range(Q):
    for t in range(3):
        mat2[q][ms[q][t]] = 1
dump(mat2)

# F2 上じゃなくて Q 上でランクをもとめちゃった
r = np.linalg.matrix_rank(mat)
r2 =  np.linalg.matrix_rank(mat2)
dump(r, r2)
dump(type(r))

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

print(resS, resT)
0