Submission #613320

#TimeUsernameProblemLanguageResultExecution timeMemory
613320drdilyorMatch (CEOI16_match)C++17
100 / 100
51 ms56576 KiB
#include <bits/stdc++.h> #ifdef ONPC #include "t_debug.cpp" #else #define debug(...) 42 #endif #define sz(a) ((int)(a).size()) using namespace std; using ll = long long; const int INF = 1e9; const ll INFL = 1e18; const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 rng(RANDOM); template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; } const int N = 2e5, LOGN = 17, MOD = 1e9+7; string solve(const string& s) { int n = s.size(); string res(n, '?'); vector<vector<int>> prev(n, vector<int>(128, -1)); for (int i = 0; i < n; i++) { if (i) { int j = prev[i-1][s[i]] - 1; if (j >= 0) prev[i] = prev[j]; } prev[i][s[i]] = i; } vector<char> cur; for (int i = 0; i < n; i++) { if (!cur.empty() && cur.back() == s[i]) { cur.pop_back(); } else { cur.push_back(s[i]); } } if (!cur.empty()) return "-1"; function<void(int,int)> construct = [&](int beg, int end) { if (beg > end) return; if (s[beg] == s[end]) { res[beg] = '('; res[end] = ')'; construct(beg+1, end-1); return; } int j = prev[end][s[beg]]; debug(s, beg, end, j); res[beg] = '('; res[j] = ')'; construct(beg+1, j-1); construct(j+1, end); }; construct(0, n-1); return res; } string solve_2(const string& s) { int n = s.size(); string res(n, '?'); function<bool(int)> brute = [&](int i) { if (i < n) { res[i] = '('; if (brute(i+1)) return true; res[i] = ')'; return brute(i+1); } else { vector<int> matching(n, -1); vector<int> cur; for (int i = 0; i < n; i++) { if (res[i] == '(') { cur.push_back(i); } else { if (cur.empty()) return false; if (s[i] != s[cur.back()]) return false; cur.pop_back(); } } return cur.empty(); } }; return brute(0) ? res : "-1"; } signed main() { int t = 1; #ifdef ONPC cin >> t; #endif while (t-- && cin) { string s; cin >> s; if (!cin) break; #ifdef ONPC cout << "Case " << s << '\n'; string res1 = solve(s), res2 = solve_2(s); cout << res1 << endl; if (res1 != res2) { cout << res2 << endl; cout << "Case " << s << '\n'; assert(false); } #else cout << solve(s); #endif } return 0; } /* █████ █████ ███ ████ ▒▒███ ▒▒███ ▒▒▒ ▒▒███ ███████ ████████ ███████ ████ ▒███ █████ ████ ██████ ████████ ███▒▒███ ▒▒███▒▒███ ███▒▒███ ▒▒███ ▒███ ▒▒███ ▒███ ███▒▒███▒▒███▒▒███ ▒███ ▒███ ▒███ ▒▒▒ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒▒▒ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒▒████████ █████ ▒▒████████ █████ █████ ▒▒███████ ▒▒██████ █████ ▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒███ ▒▒▒▒▒▒ ▒▒▒▒▒ ███ ▒███ ▒▒██████ ▒▒▒▒▒▒ */

Compilation message (stderr)

match.cpp: In lambda function:
match.cpp:5:24: warning: statement has no effect [-Wunused-value]
    5 |     #define debug(...) 42
      |                        ^~
match.cpp:49:9: note: in expansion of macro 'debug'
   49 |         debug(s, beg, end, j);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...