QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#615502 | #4212. Brackets | thomaswmy | WA | 1ms | 5824kb | C++14 | 929b | 2024-10-05 19:05:36 | 2024-10-05 19:05:36 |
Judging History
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: ':('