結果
| 問題 | No.3539 Parentheses Square |
| コンテスト | |
| ユーザー |
 はるるん
|
| 提出日時 | 2026-05-08 22:09:41 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,673 bytes |
| 記録 | |
| コンパイル時間 | 336 ms |
| コンパイル使用メモリ | 84,992 KB |
| 実行使用メモリ | 62,976 KB |
| 最終ジャッジ日時 | 2026-05-08 22:09:53 |
| 合計ジャッジ時間 | 10,772 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 18 WA * 23 |
ソースコード
# 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] = r[i+1] - 1
elif t[i] == ")":
l[i] = l[i+1] + 1
r[i] = r[i+1] + 1
else:
l[i] = max(0, l[i+1] - 1)
r[i] = r[i+1] + 1
if l[i] > r[i]:
print(-1)
exit()
if 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)
s_ = n + (n * n)
t_ = s_ + 1
idx = n
idxs = dict()
sss = []
for i in range(n):
g.add_edge(s_, i, 1)
t = SI()
ss = calc(t)
for s in ss:
if s in idxs:
g.add_edge(i, idxs[s], 1)
else:
g.add_edge(i, idx, 1)
idxs[s] = idx
idx += 1
sss.append(s)
for i in range(n, idx):
g.add_edge(i, t_, 1)
f = g.flow(s_, t_)
if f != n:
print(-1)
exit()
ans = [None] *n
for e in g.edges():
if e["flow"] == 1 and 0 <= e["from"] < n:
ans[e["from"]] = sss[e["to"] - n]
for s in ans:
print(s)