Submission #680333

#	Time	Username	Problem	Language	Result	Execution time	Memory
680333		peijar	Match (CEOI16_match)	C++17	0 / 100	1 ms	468 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 lastGood[MAXN][ALPHA];

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);
  if (nxt[0] == -1) {
    cout << -1 << endl;
    return 0;
  }

  for (int i = N - 1; i >= 0; --i) {
    for (int alpha = 0; alpha < ALPHA; ++alpha)
      lastGood[i][alpha] = -1;
    lastGood[i][s[i] - 'a'] = i;
    if (nxt[i] != -1) {
      for (int alpha = 0; alpha < ALPHA; ++alpha)
        lastGood[i][alpha] = max(lastGood[i][alpha], lastGood[nxt[i]][alpha]);
    }
  }

  string ret(N, '.');

  auto Solve = [&](auto solve, int deb, int fin) {
    assert((fin - deb) % 2 == 0);
    if (deb == fin)
      return;
    int split = lastGood[deb + 1][s[deb] - 'a'];
    ret[deb] = '(';
    ret[split] = ')';
    solve(solve, deb + 1, split);
    solve(solve, split + 1, fin);
  };
  Solve(Solve, 0, N);
  cout << ret << endl;
}

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