oj.uz

답안 #612660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
612660 2022-07-29T19:38:04 Z GusterGoose27 괄호 문자열 (CEOI16_match) C++11
10 / 100
 6 ms 2644 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<char, int> pci;

const int inf = 1e9;

class stree {
public:
	int mn_contain = inf;
	int lp, rp;
	int lz = 0;
	stree *l = nullptr;
	stree *r = nullptr;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp != rp) {
			int m = (lp+rp)/2;
			l = new stree(lp, m);
			r = new stree(m+1, rp);
		}
	}
	void prop() {
		if (l) {
			l->lz += lz;
			l->mn_contain += lz;
			r->lz += lz;
			r->mn_contain += lz;
		}
		lz = 0;
	}
	void update(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		prop();
		if (lp >= lv && rp <= rv) {
			mn_contain += v;
			lz += v;
			return;
		}
		l->update(lv, rv, v);
		r->update(lv, rv, v);
		mn_contain = min(l->mn_contain, r->mn_contain);
	}
	void update(int v, bool b = 1) {
		if (lp > v || rp < v) return;
		if (lp == rp) {
			mn_contain = 0;
			return;
		}
		l->update(v, b);
		r->update(v, b);
		mn_contain = min(l->mn_contain, r->mn_contain);
	}
	int mx_right(int lv, int rv) {
		prop();
		if (lp > rv || rp < lv || mn_contain) return 0;
		if (lp == rp) {
			return lp;
		}
		int rq = r->mx_right(lv, rv);
		if (rq > 0) return rq;
		return l->mx_right(lv, rv);
	}
};

const int MAXN = 1e5;
int n;
stree *trees[26];
bool seq[MAXN];
int nums[MAXN];
int other[MAXN];
string s;

void make(int l, int r) {
	if (r < l) return;
	int pr = trees[nums[l]]->mx_right(l, r);
	assert(pr > l);
	assert(seq[pr]);
	assert(nums[l] == nums[pr]);
	assert(!seq[l]);
	assert(seq[r]);
	int va = other[l];
	if (pr == va) {
		for (int i = 0; i < 26; i++) trees[i]->update(l+1, pr-1, -1);
	}
	else {
		int vb = other[pr];
		other[va] = vb;
		other[vb] = va;
		other[l] = pr;
		other[pr] = l;
		seq[l] = seq[va] = 0;
		seq[vb] = seq[pr] = 1;
		for (int i = 0; i < 26; i++) {
			trees[i]->update(l+1, va-1, -1);
			trees[i]->update(vb+1, pr-1, -1);
			trees[i]->update(va+1, vb-1, 1);
		}
	}
	make(l+1, pr-1);
	make(pr+1, r);
}

void check(int l, int r) {
	if (r < l) return;
	assert((r-l) % 2);
	assert(!seq[l] && seq[r]);
	assert(other[other[l]] == l);
	assert(seq[other[l]]);
	assert(nums[l] == nums[other[l]]);
	check(l+1, other[l]-1);
	check(other[l]+1, r);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> s;
	n = s.size();
	for (int i = 0; i < 26; i++) trees[i] = new stree(0, n-1);
	for (int i = 0; i < n; i++) {
		nums[i] = s[i]-'a';
		trees[nums[i]]->update(i);
	}
	vector<pii> open;
	for (int i = 0; i < n; i++) {
		if (!open.empty() && open.back().first == nums[i]) {
			int prev = open.back().second;
			other[prev] = i;
			other[i] = prev;
			seq[i] = 1;
			open.pop_back();
		}
		else open.push_back(pii(nums[i], i));
	}
	if (!open.empty()) {
		cout << "-1\n";
		return 0;
	} // mission failed... SUCCESSFULLY!
	for (int i = n-1; i >= 0; i--) {
		if (!seq[i]) {
			for (int j = 0; j < 26; j++) trees[j]->update(i+1, other[i]-1, 1);
		}
	}
	make(0, n-1);
	check(0, n-1);
	char convert[2];
	convert[0] = '(';
	convert[1] = ')';
	for (int i = 0; i < n; i++) {
		cout << convert[seq[i]];
	}
	cout << "\n";
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 6 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 6 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -