Submission #250565

#	Time	Username	Problem	Language	Result	Execution time	Memory
250565		Osama_Alkhodairy	Match (CEOI16_match)	C++17	37 / 100	2065 ms	1000 KiB

match

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n;
string s;

void apply(vector <char> &g, char c){
    if(g.size() > 0 && g.back() == c) g.pop_back();
    else g.push_back(c);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    n = s.size();
    s = ';' + s;
    vector <char> cur;
    string ans(n + 1, ';');
    vector <int> r(n + 1, n);
    for(int i = 1 ; i <= n ; i++){
        if(ans[i] != ';') continue;
        vector <char> c = cur;
        int t = -1;
        for(int j = i ; j <= r[i] ; j++){
            apply(c, s[j]);
            if(c == cur && s[j] == s[i]) t = j;
        }
        if(t == -1) finish(-1);
        ans[i] = '(';
        ans[t] = ')';
        for(int j = i ; j <= t ; j++){
            r[j] = t;
        }
        apply(cur, s[i]);
    }
    cout << ans.substr(1) << endl;
}

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