Submission #51389

#	Time	Username	Problem	Language	Result	Execution time	Memory
51389		spencercompton	Match (CEOI16_match)	C++17	0 / 100	2 ms	492 KiB

match

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

int main(){
	string str;
	cin >> str;
	int n = (int)str.length();
	vector<int> li[26];
	for(int i = 0; i<n; i++){
		li[str[i]-'a'].push_back(i);
	}
	bool ok = true;
	for(int i = 0; i<26; i++){
		ok &= li[i].size()%2==0;
	}
	if(!ok){
		cout << -1 << endl;
		return 0;
	}
	int bef[n];
	bool left[n];
	for(int i = 0; i<n; i++){
		bef[i] = -1;
		left[i] = false;
	}
	for(int i =0; i<26; i++){
		for(int j = 0; j<li[i].size()/2; j++){
			int ri = li[i].size()-1-j;
			bef[li[i][ri]] = li[i][j];
			left[li[i][j]] = true;
			left[li[i][ri]] = false;
		}
	}
	int ch = 0;
	int last[n+2];
	for(int i = 0; i<=n+1; i++){
		last[i] = -1;
	}
	for(int i =0 ; i<n; i++){
		if(left[i]){
			last[ch++] = i;
		}
		else{
			ch--;
			if(ch<0){
				ok = false;
				break;
			}
			ok &= bef[i]==last[ch];
			last[ch] =-1;
		}
	}
	if(!ok){
		cout << -1 << endl;
	}
	else{
		string t = "";
		for(int i= 0 ; i<n; i++){
			if(left[i]){
				t += "(";
			}
			else{
				t += ")";
			}
		}
		cout << t << endl;
	}
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<li[i].size()/2; j++){
                  ~^~~~~~~~~~~~~~~

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