oj.uz

Submission #179096

# Submission time Handle Problem Language Result Execution time Memory
179096 2020-01-08T09:36:54 Z AlexPop28 Match (CEOI16_match) C++11
100 / 100
 40 ms 16124 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 632 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 4 ms 1272 KB Output is correct
9 Correct 2 ms 1400 KB Output is correct
10 Correct 4 ms 1400 KB Output is correct
11 Correct 4 ms 1532 KB Output is correct
12 Correct 19 ms 9592 KB Output is correct
13 Correct 20 ms 10360 KB Output is correct
14 Correct 22 ms 11512 KB Output is correct
15 Correct 24 ms 13304 KB Output is correct
16 Correct 25 ms 13304 KB Output is correct
17 Correct 26 ms 14072 KB Output is correct
18 Correct 28 ms 13560 KB Output is correct
19 Correct 29 ms 14840 KB Output is correct
20 Correct 24 ms 9976 KB Output is correct
21 Correct 40 ms 16124 KB Output is correct