| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 608400 |
2022-07-27T07:27:38 Z |
SeDunion |
Match (CEOI16_match) |
C++17 |
|
36 ms |
340 KB |
#include<iostream>
#include<assert.h>
#include<vector>
#include<string>
#define cerr if(false)cerr
using namespace std;
int n;
string s, ans;
const int N = 2022;
int dp[N][N];
int us[N][N];
int solve(int l, int r) {
if (l > r) return 1;
if (us[l][r]) return dp[l][r];
us[l][r] = 1;
for (int i = r ; i > l ; i -= 2) {
if (s[i] == s[l] && solve(l+1, i-1) && solve(i + 1, r)) {
return dp[l][r] = 1;
}
}
return dp[l][r];
}
int L[22][26], R[22][26];
void get(int l, int r) {
if (l + 1 == r) {
ans[l] = '(';
ans[r] = ')';
return;
}
if (l > r) return;
int i = L[r][s[l]-'a'];
cerr << l << " " << r << " " << i << endl;
if (i != -1) {
ans[l] = '(';
ans[i] = ')';
get(l+1,i-1);
get(i+1,r);
return;
}
i = R[l][s[r]-'a'];
if (i != -1) {
ans[i] = '(';
ans[r] = ')';
get(l,i-1);
get(i+1,r-1);
return;
}
/*
for (int i = r ; i > l ; i -= 2) {
if (s[i] == s[l] && solve(i + 1, r)) {
assert(solve(l+1,i-1));
//if (s[i] == s[l] && solve(l+1, i-1) && solve(i + 1, r)) {
ans[l] = '(';
ans[i] = ')';
get(l + 1, i - 1);
get(i + 1, r);
return;
}
}*/
}
int main() {
ios_base::sync_with_stdio(0);
cin >> s;
n = s.size();
for (int i = 0 ; i < n ; ++ i) cerr << i;
cerr << endl;
for (int i = 0 ; i < n ; ++ i) {
for (int c = 0 ; c < 26 ; ++ c) {
L[i][c] = -1;
R[i][c] = -1;
}
}
for (int i = n-1 ; i >= 0 ; -- i) {
if (i+2<n && s[i + 1] == s[i]) {
R[i][s[i+2]-'a'] = i+2;
}
R[i][s[i]-'a']=i;
for (int rep = 0 ; rep < 26 ; ++ rep) {
for (int a = 0 ; a < 26 ; ++ a) {
for (int b = 0 ; b < 26 ; ++ b) {
if (R[i][b] != -1)
R[i][a] = max(R[i][a], R[R[i][b]][a]);
}
}
}
}
for (int i = 0 ; i < n ; ++ i) {
if (i>=2 && s[i - 1] == s[i]) {
L[i][s[i-2]-'a'] = i-2;
}
L[i][s[i]-'a']=i;
for (int rep = 0 ; rep < 26 ; ++ rep) {
for (int a = 0 ; a < 26 ; ++ a) {
for (int b = 0 ; b < 26 ; ++ b) {
if (L[i][b] >= 0)
L[i][a] = max(L[i][a], L[L[i][b]][a]);
}
}
}
}
for (int i = 0 ; i < n ; ++ i) {
for (int j = 0 ; j < 26 ; ++ j) {
if (L[i][j] == -1) cerr << "- ";
else cerr << L[i][j] << " ";
}
cerr << endl;
}
cerr << endl;
for (int i = 0 ; i < n ; ++ i) {
for (int j = 0 ; j < 26 ; ++ j) {
if (R[i][j] == -1) cerr << "- ";
else cerr << R[i][j] << " ";
}
cerr << endl;
}
if (!solve(0, n-1)) {
cout << -1;
return 0;
}
ans = string(n, '-');
get(0, n - 1);
for (int i = 0 ; i < n ; ++ i) cerr << i;
cerr << endl;
cout << ans;
}
Compilation message
match.cpp: In function 'int main()':
match.cpp:112:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
112 | if (L[i][j] == -1) cerr << "- ";
| ^
match.cpp:120:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
120 | if (R[i][j] == -1) cerr << "- ";
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
36 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
36 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
