Submission #604442

#	Time	Username	Problem	Language	Result	Execution time	Memory
604442		MetalPower	Match (CEOI16_match)	C++14	10 / 100	2 ms	2644 KiB

match

#include <bits/stdc++.h>
using namespace std;

const int MX = 1e5 + 10;

int N, ans[MX]; string s;
vector<int> arr[MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> s;
	N = s.length();

	for(int i = 0; i < N; i++)
		arr[s[i] - 'a'].push_back(i);
	
	bool f = true;
	for(int i = 0; i < 26; i++){
		if(arr[i].size() % 2 == 1){
			f = false;
			break;
		}
	}

	if(!f){
		cout << -1 << '\n';
		return 0;
	}

	vector<int> stk; // close brackets
	stk.push_back(N);

	for(int i = 0; i < N; i++){
		int ch = s[i] - 'a';
		if(ans[i] == 0){
			int fn = stk.back(), idx = lower_bound(arr[ch].begin(), arr[ch].end(), fn) - arr[ch].begin();
			if(idx > 0 && arr[ch][idx - 1] > i){
				ans[arr[ch][idx - 1]] = -1;
				ans[i] = 1;
				stk.push_back(arr[ch][idx - 1]);
			}else{
				f = false;
				break;
			}
		}else{
			stk.pop_back();
		}
	}

	if(!f){
		cout << -1 << '\n';
		return 0;
	}

	for(int i = 0; i < N; i++){
		if(ans[i] == 1) cout << '(';
		else cout << ')';
	}
	cout << '\n';
}

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