제출 #611270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611270		GusterGoose27	괄호 문자열 (CEOI16_match)	C++11	0 / 100	1 ms	212 KiB

match

#include <bits/stdc++.h>

using namespace std;

typedef pair<char, int> pci;

const int MAXN = 1e5;
int nextocc[MAXN];
int uf[MAXN+1];
int n;
bool seq[MAXN+1];

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	bool has_extend = 0;
	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 update(int v) { // set v to 1
		if (lp > v || rp < v) return;
		has_extend = 1;
		if (lp < rp) {
			l->update(v);
			r->update(v);
		}
	}
	bool query(int lv, int rv) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return has_extend;
		return l->query(lv, rv)|r->query(lv, rv);
	}
};

class stree2 {
public:
	int lp, rp;
	stree2 *l = nullptr;
	stree2 *r = nullptr;
	int mx_r;
	stree2(int lv, int rv) {
		lp = lv;
		rp = rv;
		mx_r = 0;
		if (lp != rp) {
			int m = (lp+rp)/2;
			l = new stree2(lp, m);
			r = new stree2(m+1, rp);
		}
	}
	void update(int i, int v) {
		if (lp > i || rp < i) return;
		mx_r = max(mx_r, v);
		if (lp < rp) {
			l->update(i, v);
			r->update(i, v);
		}
	}
	int query(int lv, int rv) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return mx_r;
		return max(l->query(lv, rv), r->query(lv, rv));
	}
};

int find(int i) {
	return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}

stree *tree1;
stree2 *tree2;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string s;
	cin >> s;
	n = s.size();
	tree1 = new stree(0, n-1);
	tree2 = new stree2(0, n-1);
	map<char, int> occ;
	for (int i = 0; i < n; i++) {
		char c = s[i];
		if (occ.find(c) != occ.end()) {
			nextocc[occ[c]] = i;
		}
		occ[c] = i;
	}
	for (pci p: occ) nextocc[p.second] = n;
	vector<pci> last;
	for (int i = 0; i < n; i++) {
		char c = s[i];
		if (!last.empty() && c == last.back().first) {
			seq[last.back().second] = 0;
			seq[i] = 1;
			tree2->update(last.back().second, i);
			last.pop_back();	
		}
		else last.push_back(pci(c, i));
	}
	if (!last.empty()) {
		cout << "-1\n";
		return 0;
	}
	fill(uf, uf+n+1, -1);
	for (int i = 0; i < n; i++) {
		if (seq[nextocc[i]]) uf[i] = nextocc[i];
	}
	for (int i = 0; i < n; i++) {
		if (!seq[i]) continue;
		int fpos = find(i);
		int epos = nextocc[fpos];
		if (epos == n) continue;
		assert(!seq[epos]);
		bool inv = tree1->query(fpos+1, epos-1);
		inv |= (tree2->query(fpos+1, epos-1) > epos);
		if (inv) continue;
		uf[fpos] = epos;
		tree1->update(epos);
		seq[i] = 0;
		seq[epos] = 1;
	}
	for (int i = 0; i < n; i++) {
		if (seq[i]) cout << ")";
		else cout << "(";
	}
	cout << "\n";
}

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