Submission #717699

#TimeUsernameProblemLanguageResultExecution timeMemory
717699stevancvMatch (CEOI16_match)C++14
100 / 100
19 ms11712 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 1e5 + 2; const int inf = 1e9; int gde[N][26]; int ans[N]; string s; void Resi(int l, int r) { if (l > r) return; int mid = gde[r][s[l] - 'a']; ans[mid] = 1; Resi(l + 1, mid - 1); Resi(mid + 1, r); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> s; int n = s.size(); stack<char> stk; for (int i = 0; i < n; i++) { if (!stk.empty() && stk.top() == s[i]) stk.pop(); else stk.push(s[i]); } if (!stk.empty()) { cout << -1 << en; return 0; } for (int i = 0; i < 26 * n; i++) gde[i / 26][i % 26] = -1; gde[0][s[0] - 'a'] = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < 26; j++) { if (s[i] - 'a' == j) gde[i][j] = i; else if (gde[i - 1][s[i] - 'a'] > 0) gde[i][j] = gde[gde[i - 1][s[i] - 'a'] - 1][j]; } } Resi(0, n - 1); for (int i = 0; i < n; i++) { if (ans[i] == 0) cout << '('; else cout << ')'; } cout << en; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...