結果
| 問題 | No.3539 Parentheses Square |
| コンテスト | |
| ユーザー |
 もの
|
| 提出日時 | 2026-03-04 16:43:54 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,807 bytes |
| 記録 | |
| コンパイル時間 | 185 ms |
| コンパイル使用メモリ | 85,248 KB |
| 実行使用メモリ | 193,152 KB |
| 最終ジャッジ日時 | 2026-05-08 20:51:24 |
| 合計ジャッジ時間 | 6,438 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 4 WA * 2 TLE * 1 -- * 34 |
ソースコード
############################################################################################
import bisect,collections,copy,heapq,itertools,math,string,sys,queue,time,random
from decimal import Decimal
from typing import List, Optional, Tuple
import sys
def I() -> str:
"""
標準入力から1行読み取る（改行なし）
Returns:
入力された文字列
"""
return input()
def IS():
"""
標準入力から1行読み取り、空白で分割する
Returns:
分割された文字列のリスト
"""
return input().split()
def II() -> int:
"""
標準入力から整数を1つ読み取る
Returns:
入力された整数
"""
return int(input())
def IIS():
"""
標準入力から1行読み取り、空白で分割して整数のリストにする
Returns:
整数のリスト
使い方:
a, b = IIS() # 2つの整数を受け取る
arr = IIS() # 任意個の整数をリストで受け取る
"""
return list(map(int, input().split()))
def LIIS():
"""
IIS() のエイリアス
標準入力から1行読み取り、空白で分割して整数のリストにする
Returns:
整数のリスト
"""
return list(map(int, input().split()))
"""
べき乗の高速計算・逆元の計算
機能:
- 繰り返し二乗法による高速なべき乗計算 O(log N)
- 逆元の計算（フェルマーの小定理） O(log mod)
- 逆元の計算（拡張ユークリッドの互除法） O(log min(a, mod))
- 組み合わせ計算（mod込み）
使い方:
# べき乗
pow_mod(2, 10, 1000000007) # 2^10 mod 10^9+7
# 逆元
inv = mod_inverse(3, 1000000007) # 3の逆元 mod 10^9+7
# 組み合わせ
comb = Combination(10**6, 10**9+7)
print(comb.nCr(10, 3)) # 10C3
"""
from typing import Tuple
def pow_mod(a: int, n: int, mod: int) -> int:
"""a^n mod mod を高速に計算する（繰り返し二乗法）
Args:
a: 底
n: 指数
mod: 法
Returns:
a^n mod mod
計算量: O(log N)
"""
result = 1
a %= mod
while n > 0:
if n & 1:
result = (result * a) % mod
a = (a * a) % mod
n >>= 1
return result
def mod_inverse_fermat(a: int, mod: int) -> int:
"""フェルマーの小定理による逆元の計算
mod が素数の場合に使用可能
a^(-1) ≡ a^(mod-2) (mod mod)
Args:
a: 逆元を求める数
mod: 法（素数）
Returns:
a の逆元 mod mod
計算量: O(log mod)
"""
return pow_mod(a, mod - 2, mod)
def extgcd(a: int, b: int) -> Tuple[int, int, int]:
"""拡張ユークリッドの互除法
ax + by = gcd(a, b) を満たす x, y を求める
Args:
a, b: 整数
Returns:
(gcd(a, b), x, y)
計算量: O(log min(a, b))
"""
if b == 0:
return a, 1, 0
g, x, y = extgcd(b, a % b)
return g, y, x - (a // b) * y
def mod_inverse_extgcd(a: int, mod: int) -> int:
"""拡張ユークリッドの互除法による逆元の計算
mod が素数でなくても使用可能（gcd(a, mod) = 1 が必要）
Args:
a: 逆元を求める数
mod: 法
Returns:
a の逆元 mod mod（存在しない場合は -1）
計算量: O(log min(a, mod))
"""
g, x, _ = extgcd(a, mod)
if g != 1:
return -1 # 逆元が存在しない
return x % mod
class Combination:
"""組み合わせ計算（mod 込み）
階乗と逆元を前計算して高速に nCr を計算する
"""
def __init__(self, n: int, mod: int):
"""
Args:
n: 計算する組み合わせの最大値
mod: 法（素数）
計算量: O(N)
"""
self.n = n
self.mod = mod
# 階乗を前計算
self.fact = [1] * (n + 1)
for i in range(1, n + 1):
self.fact[i] = (self.fact[i - 1] * i) % mod
# 逆元を前計算
self.inv_fact = [1] * (n + 1)
self.inv_fact[n] = mod_inverse_fermat(self.fact[n], mod)
for i in range(n - 1, -1, -1):
self.inv_fact[i] = (self.inv_fact[i + 1] * (i + 1)) % mod
def nCr(self, n: int, r: int) -> int:
"""nCr mod mod を計算する
Args:
n, r: 組み合わせのパラメータ
Returns:
nCr mod mod
計算量: O(1)
"""
if n < 0 or r < 0 or n < r:
return 0
return (self.fact[n] * self.inv_fact[r] % self.mod *
self.inv_fact[n - r] % self.mod)
def nPr(self, n: int, r: int) -> int:
"""nPr mod mod を計算する（順列）
Args:
n, r: 順列のパラメータ
Returns:
nPr mod mod
計算量: O(1)
"""
if n < 0 or r < 0 or n < r:
return 0
return (self.fact[n] * self.inv_fact[n - r] % self.mod)
def nHr(self, n: int, r: int) -> int:
"""重複組み合わせ nHr = (n+r-1)Cr
Args:
n, r: パラメータ
Returns:
nHr mod mod
計算量: O(1)
"""
return self.nCr(n + r - 1, r)
# def make_divisors(n: int) -> list[int]:
# """整数 n の約数をすべて列挙する
# Args:
# n: 約数を列挙する整数（n >= 1）
# Returns:
# n の約数のリスト（昇順）
# 計算量: O(√N)
# """
# lower_divisors = []
# upper_divisors = []
# i = 1
# while i * i <= n:
# if n % i == 0:
# lower_divisors.append(i)
# if i != n // i:
# upper_divisors.append(n // i)
# i += 1
# return lower_divisors + upper_divisors[::-1]
# sys.setrecursionlimit(10**7)
alpha="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
def bit_count(x):
return bin(x).count("1")
def yesno(f):
if f:print("Yes")
else:print("No")
MOD=998244353
from functools import lru_cache
INF=10**18
import pypyjit
# pypyjit.set_param("trace_limit=24000,vec=1")
pypyjit.set_param('max_unroll_recursion=-1')
####################################################
n=II()
T=[I() for i in range(n)]
li=[set() for i in range(n)]
# li2=[[] for i in range(n)]
for i in range(n):
for j in range(1<<n):
cnt=0
s=""
for k in range(n):
if T[i][k]=="(":
s+="("
cnt+=1
elif T[i][k]==")":
s+=")"
cnt-=1
else:
if (1<<k)&j:
s+="("
cnt+=1
else:
s+=")"
cnt-=1
if cnt<0:
break
else:
if cnt==0:
li[i].add(s)
# li2[i].append(s)
path=[[] for i in range(n)]
for i in range(n):
for j in range(n):
if i==j:continue
if li[i]>=li[j]:
path[i].append(j)
ans=["" for i in range(n)]
used=[0]*n
def dfs(v):
child=set()
for i in path[v]:
if used[i]:continue
used[i]=1
dfs(i)
child|={tuple(li[i])[0]}
cc=li[v]-child
if len(cc):
ans[v]=tuple(cc)[0]
else:
print(-1)
exit()
return child|{ans[v]}
for i in range(n):
if used[i]:continue
used[i]=1
dfs(i)
for i in ans:
print(i)