QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80657#4212. BracketsLYC_musicWA 3ms11748kbC++142.0kb2023-02-24 15:58:062023-02-24 15:58:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-24 15:58:07]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:11748kb
  • [2023-02-24 15:58:06]
  • 提交

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();
    }
}

詳細信息

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'