Submission #63413388

Source Code Expand

MOD = 998244353
N = int(input())
A = [int(s) for s in input().split()]
A.sort()
A = [0] + A


fact = [1] * (2 * N + 1)
for i in range(2 * N):
    fact[i + 1] = fact[i] * (i + 1) % MOD

fact_inv = [1] * (2 * N + 1)
fact_inv[2 * N] = pow(fact[2 * N], -1, MOD)
for i in range(2 * N, 0, -1):
    fact_inv[i - 1] = fact_inv[i] * i % MOD

Binom = [1] * (2 * N + 1)
for i in range(2 * N + 1):
    Binom[i] = (fact_inv[i] * fact_inv[2 * N - i] % MOD) * fact[2 * N] % MOD

Binom_sum = [[0] for _ in range(2)]
for i in range(2 * N + 1):
    Binom_sum[i & 1].append((Binom_sum[i & 1][-1] + Binom[i]) % MOD)

def f(s):
    if s == 1: return 2 * N - 1
    return (min(s, N) * Binom[s] - Binom_sum[(s + 1) & 1][(2 * min(N, s) - s + 1) // 2]) % MOD

ans = 0

for i in range(2 * N):
    tmp = f(i + 1) * (A[2 * N - i] - A[2 * N - 1 - i]) % MOD
    ans += tmp * fact_inv[2 * N] % MOD * fact[i + 1] % MOD * fact[2 * N - i - 1] % MOD

print(ans % MOD)

Submission Info

Submission Time
Task K - Shuffle and Max Bracket Score
User potato167
Language Python (PyPy 3.10-v7.3.12)
Score 100
Code Size 966 Byte
Status AC
Exec Time 131 ms
Memory 123140 KiB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 10 / 10 90 / 90
Status
AC × 3
AC × 16
AC × 34
Set Name Test Cases
Sample 00_sample_00, 00_sample_01, 00_sample_02
Subtask 00_sample_00, 00_sample_01, 00_sample_02, 01_small_00, 01_small_01, 01_small_02, 01_small_03, 01_small_04, 01_small_05, 01_small_06, 01_small_07, 01_small_08, 01_small_09, 01_small_10, 01_small_11, 01_small_12
All 00_sample_00, 00_sample_01, 00_sample_02, 01_small_00, 01_small_01, 01_small_02, 01_small_03, 01_small_04, 01_small_05, 01_small_06, 01_small_07, 01_small_08, 01_small_09, 01_small_10, 01_small_11, 01_small_12, 02_big_00, 02_big_01, 02_big_02, 02_big_03, 02_big_04, 02_big_05, 02_big_06, 02_big_07, 02_big_08, 02_big_09, 02_big_10, 02_big_11, 02_big_12, 02_big_13, 02_big_14, 02_big_15, 02_big_16, 02_big_17
Case Name Status Exec Time Memory
00_sample_00 AC 59 ms 76544 KiB
00_sample_01 AC 60 ms 76704 KiB
00_sample_02 AC 58 ms 76672 KiB
01_small_00 AC 60 ms 76536 KiB
01_small_01 AC 59 ms 76704 KiB
01_small_02 AC 60 ms 76684 KiB
01_small_03 AC 59 ms 76792 KiB
01_small_04 AC 59 ms 76744 KiB
01_small_05 AC 59 ms 76556 KiB
01_small_06 AC 59 ms 76612 KiB
01_small_07 AC 59 ms 76620 KiB
01_small_08 AC 59 ms 76628 KiB
01_small_09 AC 59 ms 76588 KiB
01_small_10 AC 59 ms 76740 KiB
01_small_11 AC 62 ms 76736 KiB
01_small_12 AC 59 ms 76536 KiB
02_big_00 AC 91 ms 96296 KiB
02_big_01 AC 124 ms 118876 KiB
02_big_02 AC 104 ms 107084 KiB
02_big_03 AC 122 ms 118484 KiB
02_big_04 AC 86 ms 92204 KiB
02_big_05 AC 126 ms 119536 KiB
02_big_06 AC 126 ms 119160 KiB
02_big_07 AC 129 ms 122608 KiB
02_big_08 AC 131 ms 123140 KiB
02_big_09 AC 128 ms 120400 KiB
02_big_10 AC 128 ms 110768 KiB
02_big_11 AC 129 ms 110904 KiB
02_big_12 AC 103 ms 121808 KiB
02_big_13 AC 111 ms 110500 KiB
02_big_14 AC 119 ms 111420 KiB
02_big_15 AC 124 ms 111004 KiB
02_big_16 AC 124 ms 111300 KiB
02_big_17 AC 127 ms 110928 KiB