Submission #17754138


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit
def mpow(a, n):
    p = 1
    while n:
        if n & 1:
            p = p * a % MOD
        a = a * a % MOD
        n >>= 1
    return p


@njit
def fact_table(N):
    N += 1
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[N-1] = mpow(fact[N-1], MOD-2)
    for n in range(N-1, 0, -1):
        fact_inv[n-1] = fact_inv[n] * n % MOD
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1:] = fact[:-1] * fact_inv[1:] % MOD
    return fact, fact_inv, inv

@njit
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8[:,:],i8),cache=True)
def main(A,K):
    N = len(A)
    fact, fact_inv, inv = fact_table(N+100)
    ans = 1
    for _ in range(2):
        A = A.T
        root = np.arange(N)
        size = np.ones_like(root)
        uf = (root, size)
        for i in range(N):
            for j in range(i):
                if np.all(A[i] + A[j] <= K):
                    merge(uf, i, j)
        for r in range(N):
            if find_root(uf, r) != r:
                continue
            ans = ans * fact[size[r]] % MOD
    return ans

N, K = map(int, readline().split())
A = np.array(read().split(), np.int64).reshape(N,N)

print(main(A, K))

Submission Info

Submission Time
Task C - Shuffle Permutation
User maspy
Language Python (3.8.2)
Score 500
Code Size 1881 Byte
Status AC
Exec Time 528 ms
Memory 107144 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 25
Set Name Test Cases
Sample example_00, example_01
All example_00, example_01, handmade_00, handmade_01, max_random2_00, max_random2_01, max_random2_02, max_random2_03, max_random2_04, max_random2_05, max_random2_06, max_random_00, max_random_01, max_random_02, random_00, random_01, random_02, small2_00, small2_01, small2_02, small2_03, small2_04, small_00, small_01, small_02
Case Name Status Exec Time Memory
example_00 AC 528 ms 107128 KB
example_01 AC 525 ms 106244 KB
handmade_00 AC 500 ms 106288 KB
handmade_01 AC 503 ms 106548 KB
max_random2_00 AC 501 ms 106632 KB
max_random2_01 AC 504 ms 106292 KB
max_random2_02 AC 514 ms 106316 KB
max_random2_03 AC 507 ms 106416 KB
max_random2_04 AC 509 ms 107012 KB
max_random2_05 AC 503 ms 107004 KB
max_random2_06 AC 496 ms 106356 KB
max_random_00 AC 500 ms 106292 KB
max_random_01 AC 491 ms 106364 KB
max_random_02 AC 496 ms 107072 KB
random_00 AC 502 ms 106360 KB
random_01 AC 503 ms 106560 KB
random_02 AC 501 ms 107144 KB
small2_00 AC 498 ms 106352 KB
small2_01 AC 512 ms 106932 KB
small2_02 AC 503 ms 106312 KB
small2_03 AC 503 ms 106296 KB
small2_04 AC 503 ms 106276 KB
small_00 AC 500 ms 105852 KB
small_01 AC 502 ms 105900 KB
small_02 AC 502 ms 106976 KB