Submission #524221

#	Time	Username	Problem	Language	Result	Execution time	Memory
524221		soeil	Match (CEOI16_match)	C++11	100 / 100	13 ms	11976 KiB

match

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

#define siz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define bit(n, k) (((n) >> (k)) & 1)

using ll = long long;

template <typename lhs> inline bool ckmin(lhs & a, lhs b) {
   return b < a ? a = b, true : false;
}

template <typename lhs> inline bool ckmax(lhs & a, lhs b) {
   return b > a ? a = b, true : false;
}

#define cint(c) (c - 'a')

const int maxn = 1e5 + 10, maxc = 28;
int n, dp[maxn][maxc];
string s, res;

void solve(int l, int r) {
   int p = dp[r][cint(s[l])];
   if (p == 0 - 1) {
      cout << "-1\n";
      exit(0);
   }
   res[l] = '(';
   res[p] = ')';
   if (p + 1 < r) {
      solve(p + 1, r);
   }
   if (p - 1 > l + 1) {
      solve(l + 1, p - 1);
   }
}

void Main() {
   cin >> s;
   n = siz(s);
   res = s;
   memset(dp, 511, sizeof dp);
   for (int i = 0; i < n; i++) {
      dp[i][cint(s[i])] = i;
      // cout << i << ' ' << cint(s[i]) << " -> " << dp[i][cint(s[i])] << '\n';
      if (i) {
         for (int c = 0; c < maxc; c++) {
            if (c == cint(s[i])) {
               continue;
            }
            int p = dp[i - 1][cint(s[i])];
            if (p > 0) {
               dp[i][c] = dp[p - 1][c];
            }
         }
      }
   }
   solve(0, n - 1);
   cout << res << '\n';
}

signed main() {
   ios_base::sync_with_stdio(false); cin.tie(0);
   int xyz = 1;
   // cin >> xyz;
   while (xyz--) {
      Main();
   }
   return 0;
}

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