Submission #1117771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117771		vjudge1	Match (CEOI16_match)	C++17	0 / 100	557 ms	568 KiB

match

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

#define int long long
#define ld double


const int INF = 1e18;
const int mod = 12345;
const int sz = 1e6 + 5;

bool valid(string q)
{
    if(q.size() == 1) return false;
    vector < bool > vis(q.size() , false);
    for(int i = 0;i < q.size() - 1;i++)
    {
        if(!vis[i])
        {
            bool f = 0;
            for(int j = q.size() - 1;j >= 0;j--)
            {
                if(q[i] == '(' && q[j] == ')' && !vis[j] && j > i){
                    f = 1;
                }
                vis[i] = vis[j] = 1;
            }
            if(!f) return false;
        }
    }
    return true;
}

bool ok(string q , string s)
{
    vector < bool > vis(sz , 0);
    for(int i = 0;i < q.size() - 1;i++)
    {
        if(!vis[i])
        {
            bool f = 0;
            for(int j = q.size() - 1;j >= 0;j--)
            {
                if(s[i] == s[j] && q[i] == '(' && q[j] == ')' && !vis[j] && j > i){
                    vis[i] = vis[j] = 1;
                    f = 1;
                    if(i != j - 1){
                        string z = "";
                        for(int p = i + 1;p <= j - 1;p++)
                        {
                            z = z + q[p];
                        }
                        if(!valid(z)) return false;
                    }
                    break;
                }
            }
            if(!f) return false;
        }
    }
    return true;
}

signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   string s;
   cin >> s;
   int n = s.size();
   string ans = "";
   for(int i = 0;i < n;i++)
   {
       ans = ans + ')';
       ans = ans + ')';
   }
   string nor = ans;
   for(int bit = 0;bit <= pow(2 , n) - 1;bit++){
        string q = "";
        for(int i = 0;i < n;i++)
        {
            if((1 << i) & bit) q = q + '(';
            else q = q + ')';
        }
        if(ok(q , s))
        {
            ans = min(ans , q);
        }
   }
   if(ans == nor){
    cout << -1 << endl;
    return 0;
   }
   cout << ans << endl;
}

Compilation message (stderr)

match.cpp: In function 'bool valid(std::string)':
match.cpp:16:21: 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]
   16 |     for(int i = 0;i < q.size() - 1;i++)
      |                   ~~^~~~~~~~~~~~~~
match.cpp: In function 'bool ok(std::string, std::string)':
match.cpp:37:21: 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]
   37 |     for(int i = 0;i < q.size() - 1;i++)
      |                   ~~^~~~~~~~~~~~~~

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