1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=2e6+10;
const double eps=1e-8;
const int inf=1e9+9;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
ll x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
int n;
int sum[MAXN];
int minn[MAXN<<2],maxx[MAXN<<2];
void built(int x,int l,int r){
minn[x]=inf;maxx[x]=-inf;
if(l==r){minn[x]=maxx[x]=sum[l];return ;}
int mid=(l+r)>>1;
built(x<<1,l,mid);
built(x<<1|1,mid+1,r);
minn[x]=min(minn[x<<1],minn[x<<1|1]);
maxx[x]=max(maxx[x<<1],maxx[x<<1|1]);
}
int ans;
void query_min(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){ans=min(ans,minn[x]);return ;}
int mid=(l+r)>>1;
if(ql<=mid)query_min(x<<1,l,mid,ql,qr);
if(qr>mid)query_min(x<<1|1,mid+1,r,ql,qr);
}
void query_max(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){ans=max(ans,maxx[x]);return ;}
int mid=(l+r)>>1;
if(ql<=mid)query_max(x<<1,l,mid,ql,qr);
if(qr>mid)query_max(x<<1|1,mid+1,r,ql,qr);
}
int txt[MAXN],rank1[MAXN],sa[MAXN],td[MAXN],t1[MAXN],t2[MAXN],rank2[MAXN];
bool cmp(int f[],int t,int w,int k){return f[t]==f[w]&&f[t+k]==f[w+k];}
void Sa(char str[]){
int len=strlen(str);int m=256;
int *td=t1;int *rank1=t2;
for(int i=0;i<m;i++)txt[i]=0;
for(int i=0;i<len;i++)rank1[i]=str[i],txt[str[i]]++;
for(int i=1;i<m;i++)txt[i]+=txt[i-1];
for(int i=len-1;i>=0;i--)sa[--txt[str[i]]]=i;
for(int k=1;k<=len;k<<=1){
int p=0;
for(int i=len-k;i<len;i++)td[p++]=i;
for(int i=0;i<len;i++)if(sa[i]>=k)td[p++]=sa[i]-k;
for(int i=0;i<m;i++)txt[i]=0;
for(int i=0;i<len;i++)txt[rank1[i]]++;
for(int i=1;i<m;i++)txt[i]+=txt[i-1];
for(int i=len-1;i>=0;i--)sa[--txt[rank1[td[i]]]]=td[i];
swap(rank1,td);rank1[sa[0]]=0;
p=1;
for(int i=1;i<len;i++)rank1[sa[i]]=cmp(td,sa[i],sa[i-1],k)?p-1:p++;
if(p>=len)break;
m=p;
}
for(int i=0;i<len;i++)rank2[sa[i]]=i;
}
char str[MAXN];
int main(){
scanf("%s",str);n=strlen(str);
inc(i,0,n-1)str[n+i]=str[i];str[2*n]='\0';
inc(i,0,2*n-1)if(str[i]=='(')sum[i+1]=-1;else sum[i+1]=1;
inc(i,1,2*n)sum[i]+=sum[i-1];
built(1,1,2*n);Sa(str);
int cnt=0;
for(int i=0;i<n;i++)if(str[i]=='(')cnt++;else cnt--;
if(cnt>0){
int maxx=inf,pos=0;
for(int i=0;i<n;i++){
int l=i+1;int r=i+n;
ans=-inf;query_max(1,1,2*n,l,r);
if(ans>sum[i])continue;
ans=-inf;query_max(1,1,2*n,r,r);
if(ans-sum[i]+cnt!=0)continue;
if(maxx>rank2[i])pos=i,maxx=rank2[i];
}
for(int i=pos;i<pos+n;i++)printf("%c",str[i]);
for(int i=1;i<=cnt;i++)printf(")");
}
else{
int maxx=inf,pos=0;
for(int i=0;i<n;i++){
int l=i+1;int r=i+n;
ans=-inf;query_max(1,1,2*n,l,r);
if(ans+cnt>sum[i])continue;
ans=-inf;query_max(1,1,2*n,r,r);
if(ans-sum[i]+cnt!=0)continue;
if(maxx>rank2[i])pos=i,maxx=rank2[i];
}
cnt*=-1;
for(int i=1;i<=cnt;i++)printf("(");
for(int i=pos;i<pos+n;i++)printf("%c",str[i]);
}
return 0;
}
|