Submission #812771

#	Time	Username	Problem	Language	Result	Execution time	Memory
812771		NeroZein	Match (CEOI16_match)	C++17	100 / 100	1702 ms	12572 KiB

match

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63