oj.uz

답안 #178851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
178851 2020-01-08T08:54:50 Z AlexPop28 괄호 문자열 (CEOI16_match) C++11
10 / 100
 4 ms 504 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 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
0 / 27.0

# 결과 실행 시간 메모리 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 Incorrect 4 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 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 Incorrect 4 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -