#1163979 (PyPy3) No.3539 Parentheses Square

• 問題: No.3539 Parentheses Square
• ユーザー: detteiuu
• 提出日時: 2026-05-08 23:16:14
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 6,825 bytes
• コンパイル時間: 326 ms
• コンパイル使用メモリ: 84,992 KB
• 実行使用メモリ: 102,016 KB
• 最終ジャッジ日時: 2026-05-08 23:16:39
• 合計ジャッジ時間: 15,143 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
sample	AC * 2 WA * 1
other	AC * 20 WA * 21

ソースコード

from sys import stdin
input = stdin.readline
from collections import deque, defaultdict
import sys
sys.setrecursionlimit(10**6)

class HopcroftKarp:
    def __init__(self, N1, N2):
        self.N1 = N1
        self.N2 = N2
        self.G = [[] for _ in range(self.N1+1)]
        self.pair1 = [0]*(self.N1+1)
        self.pair2 = [0]*(self.N2+1)
        self.matching_size = -1
        
    def add_edge(self, fr, to):
        self.G[fr].append(to)
    
    def bfs(self):
        que = deque()
        for i in range(1, self.N1+1):
            if self.pair1[i] == 0:
                self.dist[i] = 0
                que.append(i)
            else:
                self.dist[i] = INF
        self.dist[0] = INF
        while que:
            n = que.popleft()
            if self.dist[n] < self.dist[0]:
                for v in self.G[n]:
                    if self.dist[self.pair2[v]] == INF:
                        self.dist[self.pair2[v]] = self.dist[n]+1
                        que.append(self.pair2[v])
        return self.dist[0] != INF

    def dfs(self, n):
        if n != 0:
            for v in self.G[n]:
                if self.dist[self.pair2[v]] == self.dist[n]+1:
                    if self.dfs(self.pair2[v]):
                        self.pair2[v] = n
                        self.pair1[n] = v
                        return True
            self.dist[n] = INF
            return False
        return True
    
    def flow(self):
        if self.matching_size != -1:
            return self.matching_size
        self.dist = [0]*(self.N1+1)
        ans = 0
        while self.bfs():
            for i in range(1, self.N1+1):
                if self.pair1[i] == 0 and self.dfs(i):
                    ans += 1
        self.matching_size = ans
        return ans
    
    def get_matching(self):
        if self.matching_size == -1:
            self.flow()
        ans = []
        for i in range(1, self.N1+1):
            if self.pair1[i] != 0:
                ans.append((i, self.pair1[i]))
        return ans
    
    def minimum_vertex_cover(self):
        if self.matching_size == -1:
            self.flow()
        return self.matching_size
    
    def maximum_independent_set(self):
        return self.N1+self.N2-self.minimum_vertex_cover()
    
    def minimum_edge_cover(self):
        F = [False]*(self.N1+self.N2+1)
        for n in range(1, self.N1+1):
            F[n] = True
            for v in self.G[n]:
                F[self.N1+v] = True
        if sum(F) < self.N1+self.N2:
            return -1
        if self.matching_size == -1:
            self.flow()
        return self.N1+self.N2-self.matching_size
    
    def preparation(self):
        if self.matching_size == -1:
            self.flow()
        L = self.N1+self.N2
        G = [[] for _ in range(L+1)]
        for n in range(1, self.N1+1):
            for v in self.G[n]:
                if self.pair1[n] == v:
                    G[self.N1+v].append(n)
                else:
                    G[n].append(self.N1+v)

        visited = [False]*(L+1)
        que = deque()
        for i in range(1, self.N1+1):
            if self.pair1[i] == 0:
                visited[i] = True
                que.append(i)
        while que:
            n = que.popleft()
            for v in G[n]:
                if not visited[v]:
                    visited[v] = True
                    que.append(v)
        return visited

    def get_minimum_vertex_cover(self):
        visited = self.preparation()
        ans1 = []
        ans2 = []
        for i in range(1, self.N1+self.N2+1):
            if i <= self.N1 and not visited[i]:
                ans1.append(i)
            elif self.N1+1 <= i and visited[i]:
                ans2.append(i-self.N1)
        return ans1, ans2
    
    def get_maximum_independent_set(self):
        visited = self.preparation()
        ans1 = []
        ans2 = []
        for i in range(1, self.N1+self.N2+1):
            if i <= self.N1 and visited[i]:
                ans1.append(i)
            elif self.N1+1 <= i and not visited[i]:
                ans2.append(i-self.N1)
        return ans1, ans2
    
    def get_minimum_edge_cover(self):
        cnt = self.minimum_edge_cover()
        if cnt == -1:
            return None
        ans = []
        pair = [-1]*(self.N1+self.N2+1)
        for n in range(1, self.N1+1):
            pair[n] = self.G[n][0]
            for v in self.G[n]:
                if pair[self.N1+v] == -1:
                    pair[self.N1+v] = n
        for i in range(1, self.N1+self.N2+1):
            if i <= self.N1 and self.pair1[i] != 0:
                ans.append((i, self.pair1[i]))
            elif i <= self.N1 and self.pair1[i] == 0:
                ans.append((i, pair[i]))
            elif self.N1+1 <= i and self.pair2[i-self.N1] == 0:
                ans.append((pair[i], i-self.N1))
        return ans

HMOD = 1145141919810011
INF = 1<<60

N = int(input())
S = [input().rstrip("\n") for _ in range(N)]

def dfs(idx1, idx2, dist):
    if idx2 == -1:
        C[idx1].append("".join(A[::-1]))
        return
    if dp[idx2][dist+1] != 0:
        A.append(")")
        dfs(idx1, idx2-1, dist+1)
        A.pop()
        if N <= len(C[idx1]):
            return
    if 1 <= dist and dp[idx2][dist-1] != 0:
        A.append("(")
        dfs(idx1, idx2-1, dist-1)
        A.pop()
        if N <= len(C[idx1]):
            return

C = [[] for _ in range(N)]
for i in range(N):
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for j, s in enumerate(S[i]):
        for k in range(N+1):
            if dp[j][k] == 0: continue
            if s == "(" or s == ".":
                dp[j+1][k+1] += dp[j][k]
                dp[j+1][k+1] %= HMOD
            if (s == ")" or s == ".") and 1 <= k:
                dp[j+1][k-1] += dp[j][k]
                dp[j+1][k-1] %= HMOD
    if dp[-1][0] == 0: exit(print(-1))
    A = []
    dfs(i, N-1, 0)

idx1, idx2 = 0, 0
IDX = [-1]*N
IDXR = []
D = defaultdict(int)
DR = []
for i in range(N):
    if N <= len(C[i]): continue
    IDX[i] = idx1
    IDXR.append(i)
    idx1 += 1
    for c in C[i]:
        if c not in D:
            D[c] = idx2
            DR.append(c)
            idx2 += 1

H = HopcroftKarp(idx1, idx2)
for i in range(N):
    if N <= len(C[i]): continue
    for c in C[i]:
        H.add_edge(IDX[i]+1, D[c]+1)

mat = H.get_matching()

if len(mat) < idx1: exit(print(-1))
for l, r in mat:
    S[IDXR[l-1]] = DR[r-1]

SET = set()
for i in range(N):
    if len(C[i]) < N: continue
    for c in C[i]:
        h = 0
        for a in c:
            h *= 2
            h %= HMOD
            if a == "(":
                h += 1
            else:
                h += 2
            h %= HMOD
        if h not in SET:
            SET.add(h)
            S[i] = c
            break

for s in S:
    print(s)