Submission #609838

#	Time	Username	Problem	Language	Result	Execution time	Memory
609838		GusterGoose27	괄호 문자열 (CEOI16_match)	C++11	0 / 100	1 ms	468 KiB

match

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
int n;
string s;
int nextocc[MAXN+1][20];
map<char, int> occ;
bool failflag = 0;
bool seq[MAXN]; // 0 open, 1 close

void make(int l, int r) {
	if (r < l) return;
	if ((r-l) % 2 == 0) {
		failflag = 1;
		return;
	}
	int pos = l;
	for (int i = 19; i >= 0; i--) {
		if (nextocc[pos][i] <= r) pos = nextocc[pos][i];
	}
	if (pos == l) {
		failflag = 1;
		return;
	}
	seq[l] = 0;
	seq[pos] = 1;
	make(l+1, pos-1);
	make(pos+1, r);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; i++) {
		char c = s[i];
		if (occ.find(c) != occ.end()) {
			nextocc[occ[c]][0] = i;
		}
		occ[c] = i;
	}
	for (auto p: occ) nextocc[p.second][0] = n;
	occ.clear();
	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);
	if (failflag) {
		cout << "-1\n";
		assert(false);
	}
	else {
		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