Submission #116523

#	Time	Username	Problem	Language	Result	Execution time	Memory
116523		IOrtroiii	Match (CEOI16_match)	C++14	100 / 100	23 ms	20096 KiB

match

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

char s[N];
int let[N];
int par[N];
int nxt[N][26];
int last[N][26];
int opt[N][26];
int tot;

void solve(int l, int r) {
   if (l > r) return;
   int opt = ::opt[r][s[l] - 'a'];
   if (opt <= l) { puts("-1"); exit(0); }
   s[l] = '(', s[opt] = ')';
   solve(l + 1, opt - 1);
   solve(opt + 1, r);
}

int main() {
   scanf("%s", s + 1);
   int n = strlen(s + 1);
   int cur = 0;
   for (int i = 1; i <= n; ++i) {
      if (let[cur] == s[i]) {
         cur = par[cur];
      } else {
         int &nxt = ::nxt[cur][s[i] - 'a'];
         if (!nxt) {
            nxt = ++tot;
            par[nxt] = cur;
            let[nxt] = s[i];
         }
         cur = nxt;
      }
      last[cur][s[i] - 'a'] = i;
      for (int j = 0; j < 26; ++j) {
         opt[i][j] = last[cur][j];
      }
   }
   solve(1, n);
   puts(s + 1);
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", s + 1);
    ~~~~~^~~~~~~~~~~~~

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