#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const ll baza=29,invbaza=758620695;
const ll mod=1e9+7;
int n;
string s,sol;
vector<char> st;
vector<int> mypoz[27][2][100005];
map<ll,int> nrm;
int nxt[100005];
int sum[100005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>s;
n=s.size();
s=" "+s;
if(n%2==1)
{
cout<<-1;
return 0;
}
int nr=1;
ll h=0;
nrm[h]=1;
sum[0]=1;
for(int i=1;i<=n;i++)
{
if(!st.empty()&&st.back()==s[i])
st.pop_back();
else
st.push_back(s[i]);
}
if(!st.empty())
{
cout<<-1;
return 0;
}
for(int i=1;i<=n;i++)
{
if(!st.empty()&&st.back()==s[i])
{
st.pop_back();
h-=(s[i]-'a'+1);
h=(h*invbaza)%mod;
}
else
{
h=((h*baza)%mod+s[i]-'a'+1)%mod;
st.push_back(s[i]);
}
if(nrm[h]==0)
{
nr++;
nrm[h]=nr;
}
sum[i]=nrm[h];
mypoz[s[i]-'a'+1][i%2][sum[i]].push_back(i);
}
set<int> last;
sol.resize(n+1);
for(int i=1;i<=n;i++)
{
if(sol[i]!=')')
{
sol[i]='(';
int maxpoz=n+1;
if(!last.empty())
maxpoz=*last.begin();
int par=1-i%2;
int lit=s[i]-'a'+1;
int lft=0;
int rgt=mypoz[lit][par][sum[i-1]].size();
rgt--;
int poz=0;
while(lft<=rgt)
{
int mij=(lft+rgt)/2;
if(mypoz[lit][par][sum[i-1]][mij]<maxpoz)
{
poz=mypoz[lit][par][sum[i-1]][mij];
lft=mij+1;
}
else
rgt=mij-1;
}
sol[poz]=')';
last.insert(poz);
}
else
last.erase(i);
}
for(int i=1;i<=n;i++)
cout<<sol[i];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
127052 KB |
Output is correct |
2 |
Correct |
60 ms |
127044 KB |
Output is correct |
3 |
Correct |
66 ms |
127100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
127052 KB |
Output is correct |
2 |
Correct |
60 ms |
127044 KB |
Output is correct |
3 |
Correct |
66 ms |
127100 KB |
Output is correct |
4 |
Correct |
57 ms |
127164 KB |
Output is correct |
5 |
Correct |
57 ms |
127192 KB |
Output is correct |
6 |
Correct |
57 ms |
127180 KB |
Output is correct |
7 |
Correct |
58 ms |
127180 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
56 ms |
127052 KB |
Output is correct |
2 |
Correct |
60 ms |
127044 KB |
Output is correct |
3 |
Correct |
66 ms |
127100 KB |
Output is correct |
4 |
Correct |
57 ms |
127164 KB |
Output is correct |
5 |
Correct |
57 ms |
127192 KB |
Output is correct |
6 |
Correct |
57 ms |
127180 KB |
Output is correct |
7 |
Correct |
58 ms |
127180 KB |
Output is correct |
8 |
Correct |
73 ms |
127372 KB |
Output is correct |
9 |
Correct |
63 ms |
127560 KB |
Output is correct |
10 |
Correct |
66 ms |
127636 KB |
Output is correct |
11 |
Correct |
62 ms |
127712 KB |
Output is correct |
12 |
Correct |
98 ms |
131872 KB |
Output is correct |
13 |
Correct |
104 ms |
132244 KB |
Output is correct |
14 |
Correct |
116 ms |
132664 KB |
Output is correct |
15 |
Correct |
74 ms |
129536 KB |
Output is correct |
16 |
Correct |
75 ms |
129552 KB |
Output is correct |
17 |
Correct |
97 ms |
131920 KB |
Output is correct |
18 |
Correct |
77 ms |
128900 KB |
Output is correct |
19 |
Correct |
122 ms |
133760 KB |
Output is correct |
20 |
Correct |
98 ms |
132172 KB |
Output is correct |
21 |
Correct |
126 ms |
133988 KB |
Output is correct |