QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#613268 | #4212. Brackets | KFC | WA | 1ms | 5692kb | C++14 | 2.1kb | 2024-10-05 13:50:42 | 2024-10-05 13:50:43 |
Judging History
answer
// Hydro submission #6700d37655b5e82bc01824b2@1728107441661
#include <bits/stdc++.h>
using namespace std;
// #define freopen
int cn, a[2000005], v[1000005][2];
char ans[2000005];
int lz[8000005], mi[8000005];
void push_down(int n) {
lz[n * 2] += lz[n];
mi[n * 2] += lz[n];
lz[n * 2 + 1] += lz[n];
mi[n * 2 + 1] += lz[n];
lz[n] = 0;
}
void push_up(int n) {
mi[n] = min(mi[n * 2], mi[n * 2 + 1]);
}
void build_tree(int n, int l, int r) {
mi[n] = cn * 2 - r + 1;
if (l == r) return;
build_tree(n * 2, l, (l + r) / 2);
build_tree(n * 2 + 1, (l + r) / 2 + 1, r);
}
void add(int n, int L, int R, int X, int l, int r) {
if (R < l || L > r) return;
if (L <= l && r <= R) {
lz[n] += X;
mi[n] += X;
}
else {
push_down(n);
add(n * 2, L, R, X, l, (l + r) / 2);
add(n * 2 + 1, L, R, X, (l + r) / 2 + 1, r);
push_up(n);
}
}
int get_min() {
return mi[1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, cnt, l;
cin >> n;
cn = n;
build_tree(1, 1, n * 2);
for (int i = 1; i <= 2 * n; i ++) {
cin >> a[i];
if (!v[a[i]][0]) {
v[a[i]][0] = i;
}
else {
v[a[i]][1] = i;
}
}
if (n & 1) {
cout << ":(\n";
return 0;
}
l = 1;
for (int i = 1; i <= n; i ++) {
while (ans[l]) l ++;
add(1, 1, l, -2, 1, 2 * n);
add(1, 1, v[a[l]][0] ^ v[a[l]][1] ^ l, -2, 1, 2 * n);
if (get_min() >= 0) {
ans[l] = '(';
ans[v[a[l]][0] ^ v[a[l]][1] ^ l] = '(';
}
else {
ans[l] = ')';
ans[v[a[l]][0] ^ v[a[l]][1] ^ l] = ')';
add(1, 1, l, 2, 1, 2 * n);
add(1, 1, v[a[l]][0] ^ v[a[l]][1] ^ l, 2, 1, 2 * n);
}
}
cnt = 0;
for (int i = 1; i <= 2 * n; i ++) {
cnt += (ans[i] == '(') ? 1 : -1;
if (cnt < 0) {
cout << ":(\n";
return 0;
}
}
if (cnt != 0) {
cout << ":(\n";
return 0;
}
cout << (ans + 1) << '\n';
return 0;
}
/*
6
1 2 3 2 4 6 5 4 1 5 6 3
( ( ) ( ( ) ) ( ( ) ) )
4
1 1 3 2 2 4 4 3
( ( ) ( ( ) ) )
10
8 9 10 2 1 6 8 6 10 2 7 3 5 9 3 7 4 1 4 5
( ( ( ( ( ) ( ) ( ( ) ) ) ( ) ) ) ( ) )
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5692kb
input:
2 1 2 1 2
output:
()()
result:
ok single line: '()()'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5680kb
input:
1 1 1
output:
:(
result:
wrong answer 1st lines differ - expected: '(', found: ':('