제출 #610101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
610101		juancarlovieri	괄호 문자열 (CEOI16_match)	C++17	100 / 100	14 ms	15648 KiB

match

#include <bits/stdc++.h>
using namespace std;

int last[100005][30];
int pas[100005];
string s;
int n;

void rek(int l, int r) {
  // cout << l << ' ' << r << endl;
  if (l > r) return;
  if (l == r) assert(0);
  if (l == r - 1) {
    assert(s[l] == s[r]);
    pas[l] = r;
    return;
  }
  int tmp = last[r][s[l] - 'a'];
  pas[l] = tmp;
  rek(l + 1, tmp - 1);
  rek(tmp + 1, r);
}

int main() {
  cin >> s;
  n = s.length();
  memset(last, -1, sizeof last);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) a[i] = (s[i] - 'a');

  stack<int> st;
  for (int i = 0; i < n; ++i) {
    if (st.empty() or st.top() != a[i]) {
      st.push(a[i]);
    } else {
      st.pop();
    }
  }

  // cout << st.size() << endl;

  if (!st.empty()) {
    cout << -1 << endl;
    return 0;
  }

  for (int i = 0; i < n; ++i) {
    int cur = (s[i] - 'a');
    int prev = -1;
    if (i) {
      prev = last[i - 1][cur];
    }
    last[i][cur] = i;
    // cout << prev << endl;
    if (prev > 0) {
      for (int j = 0; j < 26; ++j) {
        if (j == cur) continue;
        last[i][j] = last[prev - 1][j];
      }
    }
  }
  // cout << last[4][0] << endl;
  memset(pas, -1, sizeof pas);
  rek(0, n - 1);
  string ans(n, '?');
  for (int i = 0; i < n; ++i) {
    if (pas[i] == -1) continue;
    ans[i] = '(';
    ans[pas[i]] = ')';
  }
  cout << ans << endl;
}

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