제출 #511422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511422		CodeTiger927	괄호 문자열 (CEOI16_match)	C++17	10 / 100	1 ms	332 KiB

match

using namespace std;

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

#define MAXN 100005

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

bool solve(int l,int r) {
	if(l > r) return true;
	auto uwu = pos[s[l] - 'a'][mask[l]];
	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();
	mask[0] = 0;
	for(int i = 0;i < N;++i) {
		mask[i + 1] = mask[i] ^ (1 << (s[i] - 'a'));
		pos[s[i] - 'a'][mask[i + 1]].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: 10 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 63