제출 #680345

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

match

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

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXP = 20;
const int MAXN = 1e5;
const int ALPHA = 26;

int nxtGood[MAXN][ALPHA];
int jmp[MAXP][MAXN];

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int N = s.size();

  vector<int> nxt(N);
  for (int i = N - 1; i >= 0; --i) {
    nxt[i] = i + 1;
    while (nxt[i] < N and s[nxt[i]] != s[i])
      nxt[i] = nxt[nxt[i]] + 1;
    if (nxt[i] > N)
      nxt[i] = N;
  }
  for (int i = 0; i < N; ++i) {
    nxt[i]++;
    if (nxt[i] == N + 1)
      nxt[i] = -1;
  }
  dbg(nxt);
  int pos = 0;
  while (pos != -1 and pos < N)
    pos = nxt[pos];
  if (pos == -1) {
    cout << -1 << endl;
    return 0;
  }
  for (int i = 0; i < N; ++i)
    jmp[0][i] = nxt[i];
  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i < N; ++i) {
      int j = jmp[p][i];
      if (j == N)
        j = -1;
      if (j != -1)
        j = jmp[p][j];
      jmp[p + 1][i] = j;
    }

  for (int i = N - 1; i >= 0; --i) {
    for (int alpha = 0; alpha < ALPHA; ++alpha)
      nxtGood[i][alpha] =
          nxt[i] == -1 or nxt[i] == N ? N : nxtGood[nxt[i]][alpha];
    nxtGood[i][s[i] - 'a'] = i;
  }

  string ret(N, '.');

  auto Solve = [&](auto solve, int deb, int fin) {
    dbg(deb, fin);
    assert((fin - deb) % 2 == 0);
    if (deb == fin)
      return;
    int cur = deb + 1;
    for (int p = MAXP - 1; p >= 0; --p)
      if (jmp[p][cur] != -1 and jmp[p][cur] != N and
          nxtGood[jmp[p][cur]][s[deb] - 'a'] < fin) {
        cur = jmp[p][cur];
      }
    int split = nxtGood[cur][s[deb] - 'a'];
    dbg(cur, split);
    ret[deb] = '(';
    ret[split] = ')';
    solve(solve, deb + 1, split);
    solve(solve, split + 1, fin);
  };
  Solve(Solve, 0, N);
  cout << ret << endl;
}

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