Submission #250569

#	Time	Username	Problem	Language	Result	Execution time	Memory
250569		Osama_Alkhodairy	Match (CEOI16_match)	C++17	10 / 100	1 ms	640 KiB

match

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

int n, base = 3271, mod = 1e9 + 7;
string s;
map <int, vector <int> > mp;

void apply(vector <char> &g, char c){
    if(g.size() > 0 && g.back() == c) g.pop_back();
    else g.push_back(c);
}
void add_char(int &cur_hash, char c){
    cur_hash = (1LL * cur_hash * base + c - 'a' + 1) % mod;
}
void del_char(int &cur_hash){
    cur_hash /= base;
}
int ub(vector <int> &cur, int idx){
    return *--upper_bound(cur.begin(), cur.end(), idx);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    n = s.size();
    s = ';' + s;
    string cur;
    vector <int> hash(n + 1);
    int cur_hash = 0;
    for(int i = 1 ; i <= n ; i++){
        if(cur.size() > 0 && s[i] == cur.back()){
            del_char(cur_hash);
            cur.pop_back();
        }
        else{
            add_char(cur_hash, s[i]);
            cur += s[i];
        }
        hash[i] = cur_hash;
    }
    if(cur.size() > 0) finish(-1);
    for(int i = 1 ; i <= n ; i++){
        int h = hash[i];
        add_char(h, s[i]);
        mp[h].push_back(i);
    }
    string ans(n + 1, ';');
    set <int> f;
    f.insert(n + 1);
    int l = 1;
    while(l <= n){
        if(f.count(l)){
            l++;
            continue;
        }
        int t = *f.upper_bound(l) - 1;
        int h = hash[l - 1];
        add_char(h, s[l]);
        int r = ub(mp[h], t);
        assert(l < r);
        ans[l] = '(';
        ans[r] = ')';
        f.insert(l);
        f.insert(r);
    }
    cout << ans.substr(1) << endl;
}

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