Submission #179096

#	Time	Username	Problem	Language	Result	Execution time	Memory
179096		AlexPop28	Match (CEOI16_match)	C++11	100 / 100	40 ms	16124 KiB

match

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


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));
  for (int i = 0; i < n; ++i) {
    // if (i != 0) dbg() name(i) name(nxt_pos[i - 1][s[i] - 'a']) endl;
    for (int j = 0; j < 26; ++j) {
      if (j == s[i] - 'a') {
        nxt_pos[i][j] = i;
      } else if (i == 0 || nxt_pos[i - 1][s[i] - 'a'] <= 0) {
        nxt_pos[i][j] = -1;
      } else {
        // dbg() name(i) name(j) "";
        nxt_pos[i][j] = nxt_pos[nxt_pos[i - 1][s[i] - 'a'] - 1][j];
        // dbg() name(nxt_pos[i][j]) endl;
      }
    }
  }
  string ans(n, '.');
  function<void(int, int)> Solve = [&](int l, int r) {
    if (l > r) return;
    // dbg() name(l) name(r) endl;
    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'];
    // dbg() name(m) endl;
    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: 27 / 27
• Subtask 3: 63 / 63