Submission #1117714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117714		vjudge1	Match (CEOI16_match)	C++17	0 / 100	71 ms	336 KiB

match

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int sz=2e5+5;

const int MOD=1e9+7;

const int INF=1e18;

bool check(string cur,string s,int b,int e)
{
    map<int,bool> used;
    
    for(int i=b;i<e;i++)
    {
        bool checker=false;
        
        if(used[i])
            continue;
        
        used[i]=true;
        
        for(int j=e-1;j>=b;j--)
        {
            if(s[j]==s[i] && cur[i]=='(' && cur[j]==')' && !used[j])
            {
                used[j]=true;
                
                checker=check(cur,s,i+1,j);
                
                break;
            }
        }
        
        if(!checker)
            return false;
    }
    
    return true;
}

void solve()
{
	string s,res="",checker="";

	cin>>s;

	for(int i=0;i< s.size();i++)
	{
		res+=')';
		
		checker+=')';
	}

	int n=s.size();

	for(int mask=1;mask<(1<<n);mask++)
	{
		string cur="";

		for(int j=0;j<n;j++)
		{
			if(mask & (1<<j))
				cur+='(';
			else
				cur+=')';
		}

        if(check(cur,s,0,s.size()))
            res=min(res,cur);
	}
	
	if(res==checker)
	    cout<<-1;
	else
	    cout<<res;
}

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

	int t=1;

	//cin>>t;

	while(t--)
	{
		solve();
	}
}

Compilation message (stderr)

match.cpp: In function 'void solve()':
match.cpp:51:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i< s.size();i++)
      |              ~^~~~~~~~~~

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