oj.uz

Submission #604444

# Submission time Handle Problem Language Result Execution time Memory
604444 2022-07-25T06:36:13 Z Monchito Match (CEOI16_match) C++17
10 / 100
 2000 ms 468 KB 
//-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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 45 ms 292 KB Output is correct
3 Correct 11 ms 212 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 45 ms 292 KB Output is correct
3 Correct 11 ms 212 KB Output is correct
4 Execution timed out 2069 ms 468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 45 ms 292 KB Output is correct
3 Correct 11 ms 212 KB Output is correct
4 Execution timed out 2069 ms 468 KB Time limit exceeded
5 Halted 0 ms 0 KB -