Submission #1117849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117849		vjudge1	Match (CEOI16_match)	C++17	0 / 100	196 ms	19016 KiB

match

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

#define int long long
#define ld double


const int INF = 1e18;
const int mod = 12345;

vector < pair < int , int > > in;

bool kes(string s , string q)
{
    int sz = s.size();
    vector < bool > vis(sz , false);
    for(int i = 0;i < sz - 1;i++)
    {
        if(vis[i]) continue;
        bool f = 0;
        for(int j = sz - 1;j >= 0;j--)
        {
            if(q[i] == '(' && q[j] == ')' && s[i] == s[j] && vis[j] == 0 && vis[i] == 0 && j > i)
            {
                vis[i] = 1;
                vis[j] = 1;
                in.push_back({i , j});
                f = 1;
            }
            if(f) break;
        }
    }
    int cnt = 0;
    for(int i = 0;i < sz;i++) cnt += vis[i];
    return cnt == sz;
}

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

signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   string s;
   cin >> s;
   int n = s.size();
   if(n == 1){
    cout << -1 << endl;
    return 0;
   }
   string ans = "";
   for(int i = 0;i < 100;i++)
   {       ans = ans + char('(' + ')');
   }
   string nor = ans;
   vector < string > pos;
   for(int bit = 0;bit < pow(2 , n);bit++)
   {
       string q = "";
       for(int i = 0;i < n;i++)
       {
           if((1 << i) & bit) q = q + '(';
           else q = q + ')';
       }
       if(!kes(s , q)) continue;
       pos.push_back(q);
   }
   in.clear();
   for(string z : pos)
   {
       kes(s , z);
       int cnt = 0;
       for(int i = 0;i < in.size();i++)
       {
           int l = in[i].first , r = in[i].second;
           string st = "";
           int sz = r - l - 1;
           if(sz == 1) break;
           if(sz == 0){
                cnt++;
                continue;
           }
           for(int j = l + 1;j <= r - 1;j++) st = st + z[j];
           if(valid(st)) cnt++;
       }
       if(cnt == in.size()){
        ans = min(ans , z);
       }
       in.clear();
   }
   if(ans == nor){
    cout << -1 << endl;
    return 0;
   }
   cout << ans << endl;
}

Compilation message (stderr)

match.cpp: In function 'int main()':
match.cpp:90:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |        for(int i = 0;i < in.size();i++)
      |                      ~~^~~~~~~~~~~
match.cpp:103:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |        if(cnt == in.size()){
      |           ~~~~^~~~~~~~~~~~

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