Submission #1117711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117711		vjudge1	Match (CEOI16_match)	C++17	0 / 100	513 ms	336 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 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]){
                    vis[i] = vis[j] = 1;
                    f = 1;
                    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 + ')';
   }
   for(int i = 1;i < n - 1;i++)
   {
       if(s[i] != s[i - 1] && s[i] != s[i + 1]){
        cout << -1 << endl;
        return 0;
       }
   }
   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);
        }
   }
   cout << ans << endl;
}

Compilation message (stderr)

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

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