Submission #812771

#TimeUsernameProblemLanguageResultExecution timeMemory
812771NeroZeinMatch (CEOI16_match)C++17
100 / 100
1702 ms12572 KiB
#include "bits/stdc++.h"
using namespace std;

string s;
vector<int> ans;

inline bool rec (int l, int r) {
  if (l > r) return true;
  if (l == r) return false; 
  if (s[l] == s[r]) return ans[l] = '(', ans[r] = ')', rec(l + 1, r - 1);
  stack<char> stk;
  stk.push(s[r]); 
  for (int i = r - 1; i > l; --i) {
    if (stk.empty() || stk.top() != s[i]) stk.push(s[i]);
    else stk.pop(); 
    if (s[i - 1] == s[l] && stk.empty()) return ans[l] = '(', ans[i - 1] = ')', rec(l + 1, i - 2) & rec(i, r); 
  }
  return false; 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> s;
  ans.resize(s.size());
  bool ok = rec(0, (int) s.size() - 1);
  if (ok) for (char c : ans) cout << c;
  else cout << -1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...