Submission #609924

#	Time	Username	Problem	Language	Result	Execution time	Memory
609924		HappyPacMan	Match (CEOI16_match)	C++14	100 / 100	20 ms	4000 KiB

match

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
const int mod1 = 1e9 + 7;
vector<pair<int,int> > mp[26];
bool res[maxn];
string s;
stack<int> stk,hash1,hash2;
 
void rec(int l,int r){
	if(l > r){
		return;
	}
	bool check = false;
	if(!stk.empty() && stk.top() == s[l]-'a'){
		stk.pop();
		hash1.pop();
		check = true;
	}else{
		int nhash1 = (27ll*hash1.top()+s[l]-'a'+1) % mod1;
		stk.push(s[l]-'a');
		hash1.push(nhash1);
	}
	int nxt = (*prev(upper_bound(mp[s[l]-'a'].begin(),mp[s[l]-'a'].end(),make_pair(hash1.top(),r)))).second;
	res[nxt] = true;
	rec(l+1,nxt-1);
	if(check){
		int nhash1 = (27ll*hash1.top()+s[l]-'a'+1) % mod1;
		stk.push(s[l]-'a');
		hash1.push(nhash1);
	}else{
		stk.pop();
		hash1.pop();
	}
	rec(nxt+1,r);
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> s;
	int n = s.size();
	hash1.push(0);
	hash2.push(0);
	for(int i=n-1;i>=0;i--){
		if(!stk.empty() && stk.top() == s[i]-'a'){
			stk.pop();
			hash1.pop();
		}else{
			int nhash1 = (27ll*hash1.top()+s[i]-'a'+1) % mod1;
			stk.push(s[i]-'a');
			hash1.push(nhash1);
		}
		mp[s[i]-'a'].push_back(make_pair(hash1.top(),i));
	}
	for(int i=0;i<26;i++){
		sort(mp[i].begin(),mp[i].end());
	}
	if(!stk.empty()){
		cout << "-1\n";
		return 0;
	}
	rec(0,n-1);
	for(int i=0;i<n;i++){
		cout << (res[i] ? ')' : '(');
	}
	cout << "\n";
}

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