Submission #612646

#	Time	Username	Problem	Language	Result	Execution time	Memory
612646		GusterGoose27	Match (CEOI16_match)	C++11	10 / 100	10 ms	2644 KiB

match

#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);
}

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);
	char convert[2];
	convert[0] = '(';
	convert[1] = ')';
	for (int i = 0; i < n; i++) {
		cout << convert[seq[i]];
		assert(other[other[i]] == i);
		assert(seq[other[i]] != seq[i]);
	}
	cout << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63