#include <bits/stdc++.h>
using namespace std;
ifstream fin("match.in");
ofstream fout("match.out");
const int NMAX = 100005;
string s;
int n;
int a[NMAX];
int sir[NMAX];
int dp[26][NMAX];
void divide(int st, int dr)
{
if(st > dr)
return;
int pos = dp[a[st]][dr];
sir[st] = 1;
sir[pos] = -1;
divide(st + 1, pos - 1);
divide(pos + 1, dr);
}
void solve()
{
cin >> s;
n = s.length();
for(int i = 0; i < n; i++)
a[i + 1] = s[i] - 'a';
stack<int> st;
for(int i = 1; i <= n; i++)
{
if(!st.empty() && st.top() == a[i])
st.pop();
else {
st.push(a[i]);
}
}
if(!st.empty())
{
cout << -1 << '\n';
return;
}
for(int i = 1; i <= n; i++)
{
dp[a[i]][i] = i;
if(i > 1)
{
for(int j = 0; j < 26; j++)
if(j != a[i] && dp[a[i]][i - 1]-1 > 0)
dp[j][i] = dp[j][dp[a[i]][i - 1]-1];
}
}
divide(1, n);
for(int i = 1; i <= n; i++)
{
if(sir[i] == 1)
cout << '(';
else cout << ')';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
1108 KB |
Output is correct |
9 |
Correct |
2 ms |
1236 KB |
Output is correct |
10 |
Correct |
1 ms |
1268 KB |
Output is correct |
11 |
Correct |
1 ms |
1236 KB |
Output is correct |
12 |
Correct |
8 ms |
7460 KB |
Output is correct |
13 |
Correct |
9 ms |
8160 KB |
Output is correct |
14 |
Correct |
10 ms |
8880 KB |
Output is correct |
15 |
Correct |
9 ms |
10156 KB |
Output is correct |
16 |
Correct |
11 ms |
10196 KB |
Output is correct |
17 |
Correct |
14 ms |
10708 KB |
Output is correct |
18 |
Correct |
11 ms |
10884 KB |
Output is correct |
19 |
Correct |
17 ms |
11600 KB |
Output is correct |
20 |
Correct |
9 ms |
7668 KB |
Output is correct |
21 |
Correct |
21 ms |
12152 KB |
Output is correct |