QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#613268#4212. BracketsKFCWA 1ms5692kbC++142.1kb2024-10-05 13:50:422024-10-05 13:50:43

Judging History

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

  • [2024-10-05 13:50:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5692kb
  • [2024-10-05 13:50:42]
  • 提交

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: ':('