oj.uz

Submission #250569

# Submission time Handle Problem Language Result Execution time Memory
250569 2020-07-18T11:46:11 Z Osama_Alkhodairy Match (CEOI16_match) C++17
10 / 100
 1 ms 640 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Runtime error 1 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Runtime error 1 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -