| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 95301 |
2019-01-29T20:11:38 Z |
pranjalssh |
Match (CEOI16_match) |
C++14 |
|
26 ms |
15992 KB |
/*
Idea: Same as official editorial
https://github.com/mostafa-saad/MyCompetitiveProgramming/blob/master/Olympiad/CEOI/official/2016/match-solution.pdf
*/
#include <bits/stdc++.h>
using namespace std;
#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
string s; cin >> s;
int n = sz(s);
vector<vi> last(n, vi(26, -1));
FOR (i, 0, n - 1) {
if (i) {
int pos = last[i-1][s[i]-'a'];
if(pos > 0) FOR (j, 0, 25) last[i][j] = last[pos-1][j];
}
last[i][s[i]-'a'] = i;
}
bool good = true;
function<void(int,int)>f = [&](int l, int r) {
if (l > r) return;
int pos = last[r][s[l]-'a'];
if (pos <= l) {good = false; return;}
s[l] = '('; s[pos] = ')';
f(l+1, pos-1);
f(pos+1, r);
};
f(0, n-1);
if (good) cout << s << "\n";
else cout << "-1\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
508 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
508 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
632 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1528 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1400 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1528 KB |
Output is correct |
| 12 |
Correct |
14 ms |
9592 KB |
Output is correct |
| 13 |
Correct |
16 ms |
10360 KB |
Output is correct |
| 14 |
Correct |
17 ms |
11512 KB |
Output is correct |
| 15 |
Correct |
20 ms |
13304 KB |
Output is correct |
| 16 |
Correct |
17 ms |
13176 KB |
Output is correct |
| 17 |
Correct |
22 ms |
13916 KB |
Output is correct |
| 18 |
Correct |
21 ms |
13432 KB |
Output is correct |
| 19 |
Correct |
24 ms |
14712 KB |
Output is correct |
| 20 |
Correct |
16 ms |
9976 KB |
Output is correct |
| 21 |
Correct |
26 ms |
15992 KB |
Output is correct |
