제출 #230710

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

match

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

const int MAXN = 100005;
const int ALPH = 26;

int N;
string S;

// Trie
int Trie[MAXN][ALPH];
int ParN[MAXN];
int ParE[MAXN];

int pos[MAXN];
vector<int> occ[MAXN];

string Answer;

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> S;
  N = S.size();
}

bool Solve(int l, int r) {
  if (l == r) return true;
  auto m = upper_bound(begin(occ[pos[l + 1]]), end(occ[pos[l + 1]]), r - 1);

  if (m == begin(occ[pos[l + 1]])) return false;
  m--;

  Answer[l] = '('; Answer[*m] = ')';
  return Solve(l + 1, *m) && Solve(*m + 1, r);
}

void Solve() {
  memset(Trie, -1, sizeof(Trie));
  memset(ParN, -1, sizeof(ParN));
  memset(ParE, -1, sizeof(ParE));
  memset(pos, -1, sizeof(pos));

  int node = 0;
  int TrieSize = 1;
  
  pos[0] = 0;
  occ[0].emplace_back(0);

  for (int i = 0; i < N; i++) {
    if (node > 0 && ParE[node] == S[i] - 'a') {
      node = ParN[node];
    } else {
      if (Trie[node][S[i] - 'a'] == -1) {
        Trie[node][S[i] - 'a'] = TrieSize++;
      }
      int prv = node;
      node = Trie[node][S[i] - 'a'];
      ParN[node] = prv;
      ParE[node] = S[i] - 'a';
    }
    pos[i + 1] = node;
    occ[node].emplace_back(i + 1);
  }
  
  Answer = string(N, '-');
  if (N % 2 == 1 || node != 0 || !Solve(0, N)) {
    cout << -1 << "\n";
  } else {
    cout << Answer << "\n";
  }
}



int main() {
  Read();
  Solve();
  return 0;
}

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