Submission #178851

#	Time	Username	Problem	Language	Result	Execution time	Memory
178851		AlexPop28	Match (CEOI16_match)	C++11	10 / 100	4 ms	504 KiB

match

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  string s; getline(cin, s);
  int n = s.size();

  vector<vector<int>> nxt_pos(n, vector<int>(26, -1));
  vector<int> lst(26, -1);
  for (int i = 0; i < n; ++i) {
    lst[s[i] - 'a'] = i;
    nxt_pos[i] = lst;
  }
  string ans(n, '.');
  function<void(int, int)> Solve = [&](int l, int r) {
    if (l > r) return;
    if ((r - l + 1) & 1) throw -1;
    if (l + 1 == r) {
      if (s[l] != s[r]) throw -1;
      ans[l] = '(';
      ans[r] = ')';
      return;
    }
    int m = nxt_pos[r][s[l] - 'a'];
    if (m <= l) throw -1;
    ans[l] = '(';
    ans[m] = ')';
    Solve(l + 1, m - 1);
    Solve(m + 1, r);
  };
  try {
    Solve(0, n - 1);
  } catch (int e) {
    cout << e << endl;
    return 0;
  }
  cout << ans << endl;
}

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