제출 #1293970

#제출 시각아이디문제언어결과실행 시간메모리
1293970eldaees131313괄호 문자열 (CEOI16_match)C++20
10 / 100
25 ms572 KiB
////////////////////////////// Author:eldaee, coder_viper!!!!!!!!!!!!!!!!!!!!!!!!11
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define int long long
#define str string
#define vec vector
#define dou double
#define ld long double
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define YES cout << "YES" << '\n'
#define Yes cout << "Yes" << '\n'
#define NO cout << "NO" << '\n'
#define No cout << "No" << '\n'
#define gcd __gcd
#define all(x) x.begin(),x.end()
#define eldaee ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

signed main()
{
    eldaee

    str s;
    cin >> s;
    int n = (int) s.size();
    string l = "";
    int tot = pow(2, n);
    for (int i = 0; i < tot; i++) {
        str b(n, ' ');
        int temp = i;
        for (int i = n - 1; i >= 0; i--) {
            if (temp % 2 == 1) {
                b[i] = '(';
            }
            else {
                b[i] = ')';
            }
            temp /= 2;
        }
        int y = 0;
        bool fl = true;
        for (int i = 0; i < n; i++) {
            if (b[i] == '(') {
                y++;
            }
            else {
                y--;
            }
            if (y < 0) {
                fl = false;
                break;
            }
        }
        if (y != 0) {
            fl = false;
        }

        if (fl) {
            vec<int> v;
            bool p = true;
            for (int i = 0; i < n; i++) {
                if (b[i] == '(') {
                        v.pb(i);
                }
                else {
                    int z = v.back();
                    v.ppb();
                    if (s[z] != s[i]) {
                        p = false;
                        break;
                    }
                }
            }
            if (p) {
                if (l == "" || b < l) {
                    l = b;
                }
            }
        }
    }
    if (l == "") {
        cout << -1 << "\n";
    }
    else {
        cout << l << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...