#include <bits/stdc++.h>
#define N 2050
using namespace std;
int n, v[N], dp[N][N], prox[N][N];
int qtd[N][30];
string s;
vector<int> pos[N];
char resp[N];
int solve(int l, int r)
{
if(r < l) return 1;
if(r - l == 1) return (v[l] == v[r]);
if(l == r) return 0;
if(dp[l][r] != -1) return dp[l][r];
prox[l][r] = -1;
int esq = lower_bound(pos[v[l]].begin(), pos[v[l]].end(), l) - pos[v[l]].begin();
int dir = min((int)(upper_bound(pos[v[l]].begin(), pos[v[l]].end(), r) - pos[v[l]].begin()), (int)pos[v[l]].size() - 1);
for(int j = dir; j >= esq; j--)
{
int p = pos[v[l]][j], nop = 0;
if(!(l < p and p <= r)) continue;
for(int t = 0; t < 30; t++)
{
if( (qtd[p - 1][t] - qtd[l][t])%2 or (qtd[r][t] - qtd[p][t])%2)
{
nop = 1;
break;
}
}
if(nop) continue;
if(solve(l + 1, p - 1) and solve(p + 1, r))
{
prox[l][r] = p;
break;
}
}
if(prox[l][r] == - 1) return dp[l][r] = 0;
return dp[l][r] = 1;
}
void getans(int l, int r)
{
if(r < l) return;
if(l == r - 1)
{
resp[l] = '(', resp[r] = ')';
return;
}
resp[l] = '(';
resp[prox[l][r]] = ')';
getans(l + 1, prox[l][r] - 1), getans(prox[l][r] + 1, r);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>s;
n = s.size();
for(int i = 1; i <= n; i++) v[i] = s[i - 1] - 'a';
for(int i = 1; i <= n; i++) pos[v[i]].push_back(i);
for(int i = 0; i < 30; i++)
for(int j = 1; j <= n; j++) qtd[j][i] = qtd[j - 1][i] + (v[j] == i);
memset(dp, -1, sizeof dp);
if(solve(1, n))
{
getans(1, n);
for(int i = 1; i<= n; i++) cout<<resp[i];
cout<<"\n";
}
else cout<<"-1\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
16888 KB |
Output is correct |
2 |
Correct |
17 ms |
16888 KB |
Output is correct |
3 |
Correct |
16 ms |
16952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
16888 KB |
Output is correct |
2 |
Correct |
17 ms |
16888 KB |
Output is correct |
3 |
Correct |
16 ms |
16952 KB |
Output is correct |
4 |
Correct |
19 ms |
19560 KB |
Output is correct |
5 |
Correct |
16 ms |
19560 KB |
Output is correct |
6 |
Correct |
17 ms |
20232 KB |
Output is correct |
7 |
Correct |
240 ms |
24580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
16888 KB |
Output is correct |
2 |
Correct |
17 ms |
16888 KB |
Output is correct |
3 |
Correct |
16 ms |
16952 KB |
Output is correct |
4 |
Correct |
19 ms |
19560 KB |
Output is correct |
5 |
Correct |
16 ms |
19560 KB |
Output is correct |
6 |
Correct |
17 ms |
20232 KB |
Output is correct |
7 |
Correct |
240 ms |
24580 KB |
Output is correct |
8 |
Runtime error |
3 ms |
24580 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
9 |
Halted |
0 ms |
0 KB |
- |