oj.uz

Submission #874878

# Submission time Handle Problem Language Result Execution time Memory
874878 2023-11-18T03:10:44 Z Muhammad_Aneeq Match (CEOI16_match) C++17
10 / 100
 2000 ms 1372 KB 
/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
string ans="";
string x;
int n;
void dfs(int i,string s="")
{
	if (i==n)
	{
		// cout<<s<<endl;
		vector<int>z;
		for (int j=0;j<n;j++)
		{
			if (s[j]==')')
			{
				if (z.size()==0)
					return;
				if (x[z.back()]!=x[j])
					return;
				z.pop_back();
			}
			else
				z.push_back(j);
		}
		if (z.size())
			return;
		if (ans=="")
			ans=s;
		ans=min(ans,s);
		return;
	}
	dfs(i+1,s+'(');
	dfs(i+1,s+')');
}
inline void solve()
{
	cin>>x;
	n=x.size();
	map<char,vector<int>>d;
	for (int i=0;i<n;i++)
		d[x[i]].push_back(i);
	for (auto i:d)
	{
		if (i.second.size()%2)
		{
			cout<<-1<<endl;return;
		}
	}
	for (auto i:d)
	{
		vector<int>x,y;
		for (auto j:i.second)
			if (j%2)
				x.push_back(j);
			else
				y.push_back(j);
		if (x.size()!=y.size())
		{
			cout<<-1<<endl;return;
		}
	}
	dfs(0);
	cout<<ans<<endl;
}
int main()
{
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 2062 ms 1372 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 30 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Execution timed out 2062 ms 1372 KB Time limit exceeded
5 Halted 0 ms 0 KB -