QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#615502#4212. BracketsthomaswmyWA 1ms5824kbC++14929b2024-10-05 19:05:362024-10-05 19:05:36

Judging History

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

  • [2024-10-05 19:05:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5824kb
  • [2024-10-05 19:05:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;

int n;
int a[N];
char S[N];
int pos[N];
int nxt[N];
set<int> st;

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n*2;i++) {
		scanf("%d",&a[i]);
		if(pos[a[i]]) nxt[pos[a[i]]]=i;
		pos[a[i]]=i;
	}
	if(n&1) {
		printf(":(");
		return 0;
	}
	for(int i=1;i<=n;i++) st.insert(i+i-1);
	for(int i=1;i<=n*2;i++) {
		if(S[i]) continue;
		auto it=st.lower_bound(nxt[i]),itt=st.lower_bound(i);
		if(it==st.end()) {
			S[i]=S[nxt[i]]=')';
			continue;
		}
		if(it==itt) itt++;
		if(itt==st.end()) {
			S[i]=S[nxt[i]]=')';
			continue;
		}
		S[i]=S[nxt[i]]='(';
		st.erase(it),st.erase(itt);
	}
	int sum=0;
	for(int i=1;i<=n*2;i++) {
		if(S[i]=='(') sum++;
		else sum--;
		if(sum<0) {
			printf(":(");
			return 0;
		}
	}
	if(sum) {
		printf(":(");
		return 0;
	}
	for(int i=1;i<=n*2;i++) printf("%c",S[i]);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5824kb

input:

2
1 2 1 2

output:

()()

result:

ok single line: '()()'

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 5764kb

input:

1
1 1

output:

:(

result:

wrong answer 1st lines differ - expected: '(', found: ':('