Submission #604444

#	Time	Username	Problem	Language	Result	Execution time	Memory
604444		Monchito	Match (CEOI16_match)	C++17	10 / 100	2069 ms	468 KiB

match

//-Si puedes imaginarlo, puedes programarlo- Alejandro Taboada
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)x.size()
#define rep(i,x,n) for(__typeof(n)i=(x);i!=(n);i+=1-2*((x)>(n)))
#define dbg(x) cout << #x << "=" << x << " ";
#define line cout << "\n.......................................................\n";

string s, ans;

bool valid(string t){
	int cnt=0;
	rep(i,0,sz(t)){
		(t[i]=='(') ? cnt++ : cnt--;	
		if(cnt<0) return false;
	}
	if(cnt>0) return false;
	rep(i,0,sz(t)){
		if(t[i]==')') continue;
		cnt=1;
		rep(j,i+1,sz(t)){
			(t[j]=='(') ? cnt++ : cnt--;	
			if(cnt==0){
				if(s[i]!=s[j]) return false;
				break;
			}
		}
	}
	return true;
}

void solve(int i, int msk){
	if(i==sz(s)){
		string t;
		rep(i,0,sz(s)) t.pb((msk & (1<<i)) ? '(' : ')');
		if(valid(t)){
			if(ans.empty()) ans=t;
			else ans=min(ans,t);
		}
		return;
	}
	solve(i+1, msk);
	solve(i+1, msk | (1<<i));
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>s;
	ans = "";
	solve(0, 0);
	if (ans.empty()) cout << "-1\n";
	else cout << ans << "\n";
	return 0;
}

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