Submission #1294022

#TimeUsernameProblemLanguageResultExecution timeMemory
1294022ayazMatch (CEOI16_match)C++20
10 / 100
31 ms572 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#define ll long long
#define int ll
#define ui unsigned int
#define pb push_back
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define vi vector<int> 
#define ost tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int sz = 1e6, inf = 1e9;
const ll mod = 998244353, INF = 1e18;
void solve(int tc) {
  string s;
  cin >> s;
  int n = isz(s);
  if (n <= 18) {
    vector<string> ans;
    for (int mask = 0; mask < (1 << n); mask++) {
      string t; t.resize(n);
      for (int i = 0; i < n; i++) {
        if (mask >> i & 1) t[i] = '(';
        else t[i] = ')';
      }
      bool KO = true;
      auto check = [](string s) -> bool {
        if (s.empty()) return true;
        stack<char> st;
        for (int i = 0; i < isz(s); i++) {
          if (s[i] == '(') st.push('(');
          else {
            if (st.empty()) return false;
            st.pop();
          }
        }
        return (st.empty());
      };
      if (!check(t)) continue;
      for (int i = 0; i < n; i++) {
        string cur;
        for (int j = i+1; j < n; j++) {
          if (t[i] == '(' && t[j] == ')' && check(cur)) {
            if (s[i] != s[j]) {
              KO = false;
              break;
            }
          }
          cur += t[j];
          if (!KO) break;
        }
      }
      if (KO) ans.push_back(t);
    }
    if (isz(ans) == 0) {
      cout << -1 << "\n";
      return;
    }
    sort(all(ans));
    cout << ans[0] << "\n";
    return;
  }
}
void precompute() {}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  freopen("in.txt", "r", stdin);
  freopen("err.log", "w", stderr);
#endif
  precompute();
  int t = 1;
  // cin >> t;
  for (int tc = 1; tc <= t; tc++) solve(tc);
  return 0;    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...