Submission #617954

#	Time	Username	Problem	Language	Result	Execution time	Memory
617954		GusterGoose27	Match (CEOI16_match)	C++11	100 / 100	43 ms	29068 KiB

match

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;

class Trie {
public:
	map<int, Trie*> nexttrie;
	Trie *par;
	map<int, vector<int>> occs;
	Trie(Trie *p = nullptr) {
		par = p;
	}
};

string s;
int n;
bool seq[MAXN];
int nums[MAXN];
int nextocc[MAXN+1][20]; // [l, r)
Trie *cur;
Trie *tries[MAXN];

void make_occ(Trie *t, int v) {
	t->occs[nums[v]].push_back(v);
}

void make(int l, int r) {
	if (r < l) return;
	cur = tries[l];
	int num = nums[l];
	assert(cur->occs[num].back() > l);
	int mn = 0;
	int mx = cur->occs[num].size();
	while (mx > mn+1) {
		int c = (mn+mx)/2;
		if (cur->occs[num][c] <= r) mn = c;
		else mx = c;
	}
	int rp = cur->occs[num][mn];
	assert(rp > l);
	seq[l] = 0;
	seq[rp] = 1;
	make(l+1, rp-1);
	make(rp+1, r);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cur = new Trie();
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; i++) {
		nums[i] = s[i]-'a';
		nextocc[i][0] = i;
	}
	vector<int> stck;
	for (int i = 0; i < n; i++) {
		tries[i] = cur;
		if (!stck.empty() && nums[i] == nums[stck.back()]) {
			cur = cur->par;
			stck.pop_back();
		}
		else {
			if (cur->nexttrie.find(nums[i]) == cur->nexttrie.end()) cur->nexttrie[nums[i]] = new Trie(cur);
			cur = cur->nexttrie[nums[i]];
			stck.push_back(i);
		}
		make_occ(cur, i);
	}
	if (!stck.empty()) {
		cout << "-1\n";
		return 0;
	}
	nextocc[n][0] = n;
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i <= n; i++) nextocc[i][j] = nextocc[nextocc[i][j-1]][j-1];
	}
	make(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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63