Submission #1214635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214635		AzeTurk810	Match (CEOI16_match)	C++20	100 / 100	18 ms	22840 KiB

match

/*
   Alone again
   Telebe of adicto yani AzeTurk810
   Lost on you
*/
#include <iostream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18
#define MOD int(1e9 + 7)
#define int ll

int n;

vector<vector<int>> dp;

bool is_valid(string &s) {
    stack<int> st;
    for(int i = 0; i < n; i++) {
        if(st.empty()) {
            st.push(s[i]);
        } else if(st.top() == s[i]) {
            st.pop();
        } else {
            st.push(s[i]);
        }
    }
    return st.empty();
}

string ans;

void build_dp(string &s) {
    for(int i = 0; i < n ; i ++) {
        for(int c = 0 ; c < 26 ; c++) {
            if(s[i] - 'a' == c) {
                dp[c][i] = i;
            } else {
                if(i != 0 && dp[s[i] - 'a'][i - 1] > 0) {
                    dp[c][i] = dp[c][dp[s[i] - 'a'][i - 1] - 1];
                }
            }
        }
    }
}

string s;

void ask(int l , int r) {
    if(l >= r) return;
    int x = dp[s[l] - 'a'][r];
    ans[l] = '(';
    ans[x] = ')';
    ask(l + 1 , x - 1);
    ask(x + 1 , r);
}

void solve() {
    cin >> s;
    n = s.size();
    ans.resize(n , '$');
    if(!is_valid(s)) {
        cout << -1 << ln;
        return;
    }
    dp.assign(26 , vector<int> (n , -1));
    build_dp(s);
    ask(0 , n - 1);
    cout << ans << ln;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--) solve();
}
//    

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