Submission #57205

#TimeUsernameProblemLanguageResultExecution timeMemory
57205RezwanArefin01Match (CEOI16_match)C++17
100 / 100
21 ms10028 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; const int N = 1e5 + 10; int trie[N][26], n, p[N], u, idx, ed[N]; vector<int> v[N]; char s[N], ans[N]; int cnt = 0; void solve(int l, int r) { if(l > r) return; vector<int> &x = v[ed[l + 1]]; auto it = --lower_bound(x.begin(), x.end(), r + 1); ans[l] = '('; ans[*it] = ')'; solve(l + 1, *it - 1); solve(*it + 1, r); } int main(int argc, char const *argv[]) { scanf(" %s", s); n = strlen(s); stack<int> st; for(int i = 0; i < n; i++) { int c = s[i] - 'a'; if(!st.size() || st.top() != c) { st.push(c); int &v = trie[u][c]; if(!v) v = ++idx; p[v] = u; u = v; } else { st.pop(); u = p[u]; } ed[i + 1] = u; } for(int i = 0; i <= n; i++) { v[ed[i]].push_back(i); } if(st.size()) return 0 * puts("-1"); solve(0, n - 1); for(int i = 0; i < n; i++) putchar(ans[i]); }

Compilation message (stderr)

match.cpp: In function 'int main(int, const char**)':
match.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", s); n = strlen(s);
  ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...