Submission #511403

#	Time	Username	Problem	Language	Result	Execution time	Memory
511403		CodeTiger927	괄호 문자열 (CEOI16_match)	C++17	0 / 100	0 ms	288 KiB

match

using namespace std;

#include <iostream>
#include <vector>
#include <algorithm>

#define MAXN 100005

int N,pre0[MAXN],pre1[MAXN];
string s;
char ans[MAXN];
vector<int> pos[2][2][2];

bool solve(int l,int r) {
	if(l > r) return true;
	auto uwu = pos[pre0[l]][pre1[l]][s[l] == 'a'];
	auto it = upper_bound(uwu.begin(),uwu.end(),r);
	if(it == uwu.begin() || *prev(it) <= l) return false;
	int owo = *prev(it);
	// cout << l << " " << owo << endl;
	ans[l] = '(';
	ans[owo] = ')';
	if(l == r - 1) return true;
	return solve(l + 1,owo - 1) & solve(owo + 1,r);
}

int main() {
	cin >> s;
	N = s.length();
	pre0[0] = pre1[0] = 0;
	for(int i = 0;i < N;++i) {
		pre0[i + 1] = pre0[i];
		pre1[i + 1] = pre1[i];
		if(s[i] == 'a') {
			pre0[i + 1] ^= 1;
		}else{
			pre1[i + 1] ^= 1;
		}
		pos[pre0[i + 1]][pre1[i + 1]][s[i] == 'a'].push_back(i);
	}
	if(solve(0,N - 1)) {
		for(int i = 0;i < N;++i) {
			cout << ans[i];
		}
		cout << endl;
	}else{
		cout << -1 << endl;
	}
	return 0;
}

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