Submission #250570

#	Time	Username	Problem	Language	Result	Execution time	Memory
250570		Osama_Alkhodairy	Match (CEOI16_match)	C++17	100 / 100	171 ms	14752 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;

int powlog(int a, int b){
    if(b == 0) return 1;
    int ret = powlog(a, b / 2);
    if(b % 2) return 1LL * ret * ret % mod * a % mod;
    return 1LL * ret * ret % mod;
}
void add_char(int &cur_hash, char c){
    cur_hash = (1LL * cur_hash * base + c - 'a' + 1) % mod;
}
void del_char(int &cur_hash, int c){
    cur_hash -= c - 'a' + 1;
    if(cur_hash < 0) cur_hash += mod;
    cur_hash = 1LL * cur_hash * powlog(base, mod - 2) % mod;
}
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, s[i]);
            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: 27 / 27
• Subtask 3: 63 / 63