結果
| 問題 | No.3539 Parentheses Square |
| コンテスト | |
| ユーザー |
 はるるん
|
| 提出日時 | 2026-05-08 22:25:30 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,586 bytes |
| 記録 | |
| コンパイル時間 | 221 ms |
| コンパイル使用メモリ | 85,120 KB |
| 実行使用メモリ | 112,128 KB |
| 最終ジャッジ日時 | 2026-05-08 22:26:06 |
| 合計ジャッジ時間 | 9,812 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 TLE * 1 -- * 12 |
ソースコード
# input
import sys
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : map(int, input().split())
LI = lambda : [int(a) for a in input().split()]
SI = lambda : input().rstrip()
LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)]
LSI = lambda n : [input().rstrip() for _ in range(n)]
MI_1 = lambda : map(lambda x:int(x)-1, input().split())
LI_1 = lambda : [int(a)-1 for a in input().split()]
mod = 998244353
inf = 1001001001001001001
ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97
ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97
yes = lambda : print("Yes")
no = lambda : print("No")
yn = lambda flag : print("Yes" if flag else "No")
prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)
alplow = "abcdefghijklmnopqrstuvwxyz"
alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]
prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
sys.set_int_max_str_digits(0)
# sys.setrecursionlimit(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
DD = defaultdict
BSL = bisect_left
BSR = bisect_right
import collections
class mf_graph:
n = 0
g = []
def __init__(self, n_):
self.n = n_
self.g = [[] for i in range(self.n)]
self.pos = []
class _edge:
to = 0
rev = 0
cap = 0
def __init__(self, to_, rev_, cap_):
self.to = to_
self.rev = rev_
self.cap = cap_
class edge:
From = 0
To = 0
Cap = 0
Flow = 0
def __init__(self, from_, to_, cap_, flow_):
self.From = from_
self.To = to_
self.Cap = cap_
self.Flow = flow_
def add_edge(self, From_, To_, Cap_):
assert 0 <= From_ and From_ < self.n
assert 0 <= To_ and To_ < self.n
assert 0 <= Cap_
m = len(self.pos)
self.pos.append((From_, len(self.g[From_])))
from_id = len(self.g[From_])
to_id = len(self.g[To_])
if From_ == To_:
to_id += 1
self.g[From_].append(self._edge(To_, to_id, Cap_))
self.g[To_].append(self._edge(From_, from_id, 0))
return m
def get_edge(self, i):
m = len(self.pos)
assert 0 <= i and i < m
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e.to][_e.rev]
return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)
def edges(self, isdict=True):
m = len(self.pos)
result = []
for i in range(m):
if isdict:
e = self.get_edge(i)
result.append(
{"from": e.From, "to": e.To, "cap": e.Cap, "flow": e.Flow}
)
else:
result.append(self.get_edge(i))
return result
def change_edge(self, i, new_cap, new_flow):
m = len(self.pos)
assert 0 <= i and i < m
assert 0 <= new_flow and new_flow <= new_cap
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e.to][_e.rev]
_e.cap = new_cap - new_flow
_re.cap = new_flow
assert id(_e) == id(self.g[self.pos[i][0]][self.pos[i][1]])
assert id(_re) == id(self.g[_e.to][_e.rev])
def flow(self, s, t, flow_limit=(1 << 63) - 1):
assert 0 <= s and s < self.n
assert 0 <= t and t < self.n
assert s != t
level = [0 for i in range(self.n)]
Iter = [0 for i in range(self.n)]
que = collections.deque([])
def bfs():
for i in range(self.n):
level[i] = -1
level[s] = 0
que.clear()
que.append(s)
while que:
v = que.popleft()
for e in self.g[v]:
if e.cap == 0 or level[e.to] >= 0:
continue
level[e.to] = level[v] + 1
if e.to == t:
return
que.append(e.to)
def dfs(v, up):
if v == s:
return up
res = 0
level_v = level[v]
for i in range(Iter[v], len(self.g[v])):
e = self.g[v][i]
assert id(e) == id(self.g[v][i])
if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
continue
d = dfs(e.to, min(up - res, self.g[e.to][e.rev].cap))
if d <= 0:
continue
self.g[v][i].cap += d
self.g[e.to][e.rev].cap -= d
res += d
if res == up:
return res
level[v] = self.n
return res
flow = 0
while flow < flow_limit:
bfs()
if level[t] == -1:
break
Iter = [0 for i in range(self.n)]
f = dfs(t, flow_limit - flow)
if not (f):
break
flow += f
return flow
def min_cut(self, s):
visited = [False for i in range(self.n)]
que = collections.deque([s])
while que:
p = que.popleft()
visited[p] = True
for e in self.g[p]:
if e.cap and not (visited[e.to]):
visited[e.to] = True
que.append(e.to)
return visited
"""
面白い
検討がつかない
200 個列挙して、重複がないようにすればいいというはなしですね
"""
# しんどい
# どうかこう
def calc(t):
ok = []
l = [0] * (n + 1)
r = [0] * (n + 1)
for i in reversed(range(n)):
if t[i] == "(":
l[i] = max(0, l[i+1] - 1)
r[i] = min(n//2, r[i+1] - 1)
elif t[i] == ")":
l[i] = l[i+1] + 1
r[i] = min(n//2, r[i+1] + 1)
else:
l[i] = max(0, l[i+1] - 1)
r[i] = min(n//2, r[i+1] + 1)
if l[i] > r[i]:
print(-1)
exit()
if not (l[0] <= 0 <= r[0]):
print(-1)
exit()
# print(l, r)
p = []
def dfs(i, d):
if len(ok) == n: return
if i == n:
if d == 0:
ok.append("".join(p))
return
if t[i] in "(." and l[i+1] <= d + 1 <= r[i+1]:
p.append("(")
dfs(i + 1, d + 1)
p.pop()
if len(ok) == n: return
if t[i] in ")." and l[i+1] <= d - 1 <= r[i+1]:
p.append(")")
dfs(i + 1, d - 1)
p.pop()
if len(ok) == n: return
dfs(0, 0)
return ok
n = II()
# g = mf_graph(n + n * n + 2)
from random import shuffle
class Bipartite_Matching:
__slots__ = ("__M", "__N", "__edges", "__size", "__matching")
def __init__(self, M: int, N: int):
""" 部集合の大きさが M, N である二部グラフを生成する.
Args:
M (int): 部集合 1 の大きさ
N (int): 部集合 2 の大きさ
"""
self.__M = M
self.__N = N
self.__edges: list[list[int]] = [[] for _ in range(M)]
@property
def M(self) -> int:
""" 部集合 1 の大きさを返す.
Returns:
int: 部集合 1 の大きさ
"""
return self.__M
@property
def N(self) -> int:
""" 部集合 2 の大きさを返す.
Returns:
int: 部集合 2 の大きさ
"""
return self.__N
def add_edge(self, a: int, b: int):
""" 辺 Aa と辺 Bb を結ぶ無向辺を追加する.
Args:
a (int): 部集合 1 側の頂点番号
b (int): 部集合 2 側の頂点番号
"""
assert 0 <= a < self.M
assert 0 <= b < self.N
self.__edges[a].append(b)
def calculate(self, matching = False):
""" 最大マッチングを計算する (結果は property メソッドで参照する).
Args:
matching (bool, optional): True にすると, 最大マッチングの一例も一緒に求める. Defaults to False.
"""
for a in range(self.M):
shuffle(self.__edges[a])
edge = self.__edges
pre = [-1] * self.M
root = [-1] * self.M
p = [-1] * self.M
q = [-1] * self.N
updated = True
size = 0
while updated:
updated = False
S = []
index = 0
for i in range(self.M):
if p[i] == -1:
root[i] = i
S.append(i)
while index < len(S):
v = S[index]
index += 1
if p[root[v]] != -1:
continue
for u in edge[v]:
if q[u] == -1:
while u != -1:
q[u] = v
p[v], u = u, p[v]
v = pre[v]
updated = True
size += 1
break
u = q[u]
if pre[u] != -1:
continue
pre[u] = v
root[u] = root[v]
S.append(u)
if updated:
pre = [-1] * self.M
root = [-1] * self.M
self.__size = size
if not matching:
self.__matching = None
A = [-1] * self.M
B = [-1] * self.N
for i in range(self.M):
if p[i] != -1:
A[i] = p[i]
B[p[i]] = i
self.__matching = (A, B)
@property
def max_matching_size(self) -> int:
""" calculate で求めた最大マッチングのサイズを求める.
Returns:
int: 最大マッチングのサイズ
"""
return self.__size
@property
def max_matching(self) -> tuple[list[int], list[int]]:
""" calculate で求めた最大マッチングの一例を求める.
Returns:
tuple[list[int], list[int]]: (A, B)
A[i] が -1 ではないとき, 辺 (i, A[i]) がマッチングとして採用されている. A[i] = -1 のときはマッチングの頂点として採用されていない.
B[j] が -1 ではないとき, 辺 (B[j], j) がマッチングとして採用されている. B[j] = -1 のときはマッチングの頂点として採用されていない.
"""
return self.__matching
# s_ = n + (n * n)
# t_ = s_ + 1
idx = 0
idxs = dict()
sss = []
g = Bipartite_Matching(n, n * n)
e = []
for i in range(n):
t = SI()
ss = calc(t)
for s in ss:
if s in idxs:
g.add_edge(i, idxs[s])
else:
g.add_edge(i, idx)
idxs[s] = idx
idx += 1
sss.append(s)
g.calculate(True)
if g.max_matching_size != n:
print(-1)
exit()
a, b = g.max_matching
# print(a, b)
ans = [None] * n
for i in range(n):
ans[i] = sss[a[i]]
for s in ans:
print(s)