QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80657 | #4212. Brackets | LYC_music | WA | 3ms | 11748kb | C++14 | 2.0kb | 2023-02-24 15:58:06 | 2023-02-24 15:58:07 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define pa pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define int ll
#define N 400005
using namespace std;
int n,a[N],bl[N];
int l[N],r[N];
int p[N];
int tag[N<<2],tr[N<<2];
void ptag(int k,int x)
{
tr[k]+=x;
tag[k]+=x;
}
void pushup(int k)
{
tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
void pushdown(int k)
{
ptag(k<<1,tag[k]);
ptag(k<<1|1,tag[k]);
tag[k]=0;
}
void build(int k,int l,int r)
{
tr[k]=0;
tag[k]=0;
if (l==r) return;
int mid=l+(r-l)/2;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int L,int R,int x)
{
if (L<=l&&r<=R)
{
ptag(k,x);
return;
}
int mid=l+(r-l)/2;
pushdown(k);
if (L<=mid) update(k<<1,l,mid,L,R,x);
if (R>mid) update(k<<1|1,mid+1,r,L,R,x);
pushup(k);
}
void BellaKira()
{
cin>>n;
for (int i=1;i<=2*n;i++)
{
cin>>a[i];
if (!l[a[i]])
l[a[i]]=i;
r[a[i]]=i;
}
if (n%2==1)
{
cout<<"No\n";
return;
}
build(1,1,2*n);
int t=n/2;
for (int i=1;i<=2*n;i++) p[i]=0;
for (int i=1;i<=2*n;i++) update(1,1,2*n,1,i,-1);
for (int i=1;i<=2*n;i++)
{
if (p[a[i]]) continue;
update(1,1,2*n,1,i,2);
update(1,1,2*n,1,r[a[i]],2);
p[a[i]]=1;
// cout<<"?"<<i<<" "<<t<<" "<<tr[1]<<" "<<i<<" "<<r[a[i]]<<'\n';
if (tr[1]>0)
{
p[a[i]]=-1;
update(1,1,2*n,1,i,-2);
update(1,1,2*n,1,r[a[i]],-2);
} else t--;
if (!t) break;
}
int x=0;
bool ans=1;
for (int i=1;i<=2*n;i++)
{
if (!p[a[i]]) p[a[i]]=-1;
x+=p[a[i]];
ans&=(x>=0);
}
// cout<<"?"<<x<<" "<<ans<<'\n';
ans&=(x==0);
if (ans)
{
for (int i=1;i<=2*n;i++)
if (p[a[i]]==1) cout<<'(';
else cout<<')';
cout<<'\n';
return;
}
cout<<"(\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11748kb
input:
2 1 2 1 2
output:
()()
result:
ok single line: '()()'
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 7504kb
input:
1 1 1
output:
No
result:
wrong answer 1st lines differ - expected: '(', found: 'No'