oj.uz

Submission #1117861

# Submission time Handle Problem Language Result Execution time Memory
1117861 2024-11-24T09:03:28 Z vjudge1 Match (CEOI16_match) C++17
10 / 100
 2000 ms 336 KB 
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define all(v) v.begin(), v.end()
#define pb push_back
#define iospeed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
bool f(string s)
{
    ll cnt1 = 0, cnt2 = 0;
    for(auto u : s)
    {
        if(u == '(')
            cnt1++;
        else
            cnt2++;
        if(cnt2 > cnt1)
            return false;
    }
    return true;
}
int main()
{
    iospeed
    string s;
    cin >> s;
    ll n = (ll)(s.size()), i, j, k;
    vector<string>vect;
    for(i = 0; i < (1 << n); i++)
    {
        ll pref[n+5];
        pref[0] = 0;
        string str = "";
        bool ok = true;
        for(j = 0; j < n; j++)
        {
            pref[j+1] = pref[j];
            if((i >> j) & 1){
                str += ")";
                pref[j+1]--;
            }
            else{
                str += "(";
                pref[j+1]++;
            }
            if(pref[j+1] < 0)
            {
                ok = false;
                break;
            }
        }
        if(!ok)
            continue;
        for(j = 1; j <= n; j++)
        {
            for(k = j + 1; k <= n; k++)
            {
                if(pref[k] - pref[j-1] == 0 && str[j-1] == '(' && str[k-1] == ')')
                {
                    if(k == j + 1 && s[k-1] != s[j-1])
                        ok = false;
                    else
                    {
                        string fg = "";
                        for(ll t = j + 1; t <= k - 1; t++)
                            fg += str[t-1];
                        if(f(fg) && s[k-1] != s[j-1])
                            ok = false;
                    }
                }
            }
        }
        if(ok && pref[n] == 0)
            vect.pb(str);
    }
    if(vect.size() == 0)
        cout << "-1\n";
    else
    {
        sort(all(vect));
        cout << vect[0] << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 45 ms 336 KB Output is correct
3 Correct 9 ms 336 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 45 ms 336 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Execution timed out 2065 ms 336 KB Time limit exceeded
5 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 Correct 45 ms 336 KB Output is correct
3 Correct 9 ms 336 KB Output is correct
4 Execution timed out 2065 ms 336 KB Time limit exceeded
5 Halted 0 ms 0 KB -