oj.uz

Submission #1117711

# Submission time Handle Problem Language Result Execution time Memory
1117711 2024-11-24T07:42:07 Z vjudge1 Match (CEOI16_match) C++17
0 / 100
 513 ms 336 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 513 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 513 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 513 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -