#1163969 (C++23) No.3539 Parentheses Square

• 問題: No.3539 Parentheses Square
• ユーザー: HoyHoyCharhang
• 提出日時: 2026-05-08 23:12:22
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 3,642 bytes
• コンパイル時間: 3,651 ms
• コンパイル使用メモリ: 366,188 KB
• 実行使用メモリ: 13,056 KB
• 最終ジャッジ日時: 2026-05-08 23:12:55
• 合計ジャッジ時間: 11,073 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

ファイルパターン	結果
sample	AC * 3
other	AC * 4 RE * 2 TLE * 1 -- * 34

ソースコード

#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,g,n) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define eb emplace_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>;
using P = pair<int,int>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}

struct HopcroftKarp {
  vector< vector< int > > graph;
  vector< int > dist, match;
  vector< bool > used, vv;

  HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {}

  void add_edge(int u, int v) {
    graph[u].push_back(v);
  }

  void bfs() {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a) {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching() {
    int ret = 0;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }

  void output() {
    for(int i = 0; i < match.size(); i++) {
      if(~match[i]) {
        cout << match[i] << "-" << i << endl;
      }
    }
  }
};

int main() {
  int n;
  cin >> n;
  vector<string> t(n);
  rep(i,0,n) cin >> t[i];
  function<void(vector<string>&, string&, string&, int, int, int)> f = [&](vector<string> &v, string &s, string &t, int idx, int val, int cnt) {
    if (len(v) > n) return;
    if (idx == n) {
      v.eb(s);
      return;
    }
    if (t[idx] == '(' || t[idx] == '.') {
      if (cnt < n/2) {
        s[idx] = '(';
        f(v, s, t, idx+1, val+1, cnt+1);
        s[idx] = '.';
      }
    }
    if (t[idx] == ')' || t[idx] == '.') {
      if (idx-cnt < n/2 && val > 0) {
        s[idx] = ')';
        f(v, s, t, idx+1, val-1, cnt);
        s[idx] = '.';
      }
    }
  };
  vector<vector<string>> u(n);
  string s(n, '.');
  rep(i,0,n) f(u[i], s, t[i], 0, 0, 0);
  // rep(i,0,n) {
  //   for (string v : u[i]) cout << v << endl;
  //   cout << endl;
  // }
  vector<pair<string,int>> x;
  rep(i,0,n) {
    for (string &v : u[i]) {
      x.eb(v, i);
    }
  }
  sort(all(x));
  vector<vector<int>> G(n);
  vector<string> y;
  rep(i,0,len(x)) {
    if (i == 0 || x[i-1].fi != x[i].fi) {
      G[x[i].se].eb(len(y));
      y.eb(x[i].fi);
    } else {
      G[x[i].se].eb(len(y)-1);
    }
  }
  // rep(i,0,len(y)) cout << y[i] << endl;
  HopcroftKarp hk(n, len(y));
  rep(i,0,n) {
    for (int j : G[i]) {
      hk.add_edge(i, j);
    }
  }
  if (hk.bipartite_matching() < n) {
    cout << -1 << endl;
  }
  vector<int> ans(n);
  rep(i,0,len(y)) {
    if (~hk.match[i]) {
      ans[hk.match[i]] = i;
    }
  }
  rep(i,0,n) cout << y[ans[i]] << endl;
  return 0;
}