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

• 問題: No.3539 Parentheses Square
• ユーザー: はるるん
• 提出日時: 2026-05-08 23:18:56
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,061 bytes
• コンパイル時間: 4,647 ms
• コンパイル使用メモリ: 391,164 KB
• 実行使用メモリ: 22,524 KB
• 最終ジャッジ日時: 2026-05-08 23:19:27
• 合計ジャッジ時間: 9,522 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 28 TLE * 1 -- * 12

コンパイルメッセージ

main.cpp:57:9: warning: 'rep' redefined
   57 | #define rep(i, n) for (ll i = 0; i < ll(n); i++)
      |         ^~~
main.cpp:27:9: note: this is the location of the previous definition
   27 | #define rep(i,l,r) for (int i = (int)(l); i < (int)(r); i++)
      |         ^~~

ソースコード

// # pragma GCC target("avx2")
// # pragma GCC optimize("O3")
// # pragma GCC optimize("unroll-loops")
#ifdef harurun
#define debug(x) cerr<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint1000000007;
// using mint = double;
#endif

//define
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long , long long>;
using vi = vector<int>;
using vll = vector<long long>;

#define rep(i,l,r) for (int i = (int)(l); i < (int)(r); i++)
#define rrep(i,l,r) for (int i = (int)(r-1); i >= (int)(l); i--)
#define len(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define elif else if
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int inf = 1e9;
const long long infl = 1LL<<60;
const int mod = 998244353;
ll pow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T, class U> bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; }
template <class T>
using spq = priority_queue<T, vector<T>, greater<T>>;

template<class T>istream& operator>>(istream& i, vector<T>& v) {for(int j = 0; j < (int)(v).size(); j++) i >> v[j]; return i;}
struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} iosetup;


using ll = long long;
#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define rep2(i, l, r) for (ll i = ll(l); i < ll(r); i++)

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;

mt19937 engine;

vector<pair<int, int>> Bipartite_Mathing(int n, int m, vector<pair<int, int>> &edges) {
  shuffle(edges.begin(),edges.end(),engine);
  vi G(edges.size()), L(n, -1), R(m, -1), deg(n + 1), a, p, q(n);
  for (auto &[x, y] : edges) deg[x]++;
  rep(i, n) deg[i + 1] += deg[i];
  for (auto &[x, y] : edges) G[--deg[x]] = y;
  while (true) {
    a.assign(n, -1), p.assign(n, -1);
    int t = 0;
    rep(i, n) {
      if (L[i] == -1) {
        q[t++] = a[i] = p[i] = i;
      }
    }
    bool match = false;
    rep(i, t) {
      int x = q[i];
      if (L[a[x]] != -1) continue;
      rep2(j, deg[x], deg[x + 1]) {
        int y = G[j];
        if (R[y] == -1) {
          while (y != -1) {
            R[y] = x;
            swap(L[x], y);
            x = p[x];
          }
          match = true;
          break;
        }
        if (p[R[y]] == -1) {
          q[t++] = y = R[y];
          p[y] = x;
          a[y] = a[x];
        }
      }
    }
    if (!match) break;
  }
  vector<pair<int, int>> res;
  rep(i, L.size()) {
    if (L[i] != -1) res.push_back({i, L[i]});
  }
  return res;
}


vector<string> calc(string t) {
    int n = len(t);
    vector<string> ok;
    vi l(n + 1, 0), r(n + 1, 0);

    rrep(i, 0, 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] = max(0, 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] || r[i] < 0){
            cout << -1 << endl;
            exit(0);
        }
    }
    
    if (not (l[0] <= 0 and 0 <= r[0])) {
        cout << -1 << endl;
        exit(0);
    }
    
    string p(n, ' ');
    auto dfs = [&](auto& dfs, int i, int d) -> void {
        if (len(ok) == n) return;
        
        if (i == n) {
            if (d == 0) ok.push_back(p);
            return;
        }
        
        if ((t[i] == '(' || t[i] == '.') and l[i+1] <= d + 1 and d + 1 <= r[i+1]) {
            p[i] = '(';
            dfs(dfs, i + 1, d + 1);
        }
        
        if (len(ok) == n) return;
        
        if ((t[i] == ')' || t[i] == '.') and l[i+1] <= d - 1 and d - 1 <= r[i+1]) {
            p[i] = ')';
            dfs(dfs, i + 1, d - 1);
        }

        if (len(ok) == n) return;
    };
    
    dfs(dfs, 0, 0);
    return ok;
}

int main(){
    int n; cin >> n;
    unordered_map<string, int> idxs;
    int idx = 0;
    vector<string> sss; 
    
    vector<pii> e;
    rep2(i, 0, n){
        string t; cin >> t;
        auto ss = calc(t);
        for (auto s : ss){
            if (not idxs.count(s)){
                idxs[s] = idx;
                idx++;
                sss.pb(s);
            }
            e.push_back({i, idxs[s]});
        }
    }
    vector<pair<int, int>> ans = Bipartite_Mathing(n, idx, e);
    if (len(ans) != n){
        cout << -1 << endl;
    }else{
        vector<string> tmp(n);
        for (auto [a, b] : ans){
            tmp[a] = sss[b];
        }
        rep2(i, 0, n){
            cout << tmp[i] << endl;
        }
    }
}