Submission #51848

#	Time	Username	Problem	Language	Result	Execution time	Memory
51848		someone_aa	Match (CEOI16_match)	C++17	100 / 100	273 ms	21516 KiB

match

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll hashmod = 1230523952352LL;
const ll k=31LL;
const int maxn = 100100;
map<ll, vector<int> >wi[26];
map<ll, vector<int> >wo[26];
string code, seq;
ll power[maxn], chash[maxn];
int n;

bool check() {
    stack<char>st;
    if(n%2==1) return false;
    for(int i=0;i<code.length();i++) {
        if(st.empty()) st.push(code[i]);
        else if(!st.empty() && st.top() == code[i]) st.pop();
        else if(!st.empty() && st.top() != code[i]) st.push(code[i]);
    }
    if(st.empty()) return true;
    else return false;
}

ll bin_search(int bukva, ll ch, int value) {
    int index = 0;
    for(int cekor = wi[bukva][ch].size();cekor>0;cekor/=2) {
        while(index+cekor < wi[bukva][ch].size() && wi[bukva][ch][index+cekor] <= value) index+=cekor;
    }
    return wi[bukva][ch][index];
}

void solve(int li=0, int ri=n-1) {
    if(ri <= li) return;
    int bukva = int(code[li] - 'a');
    int closing = bin_search(bukva, chash[li], ri);

    seq[li] = '(';
    seq[closing] = ')';

    if(closing == ri) solve(li+1, ri-1);
    else {
        solve(li+1, closing-1);
        solve(closing+1, ri);
    }
}

int main() {
    cin>>code;
    seq = code;
    n = code.length();
    if(!check()) {
        cout<<-1;
        return 0;
    }

    ll curr_hash = 0LL;
    power[0] = 1LL;
    for(int i=1;i<=n;i++) {
        power[i] = 1LL*(power[i-1] * k) % hashmod;
    }
    stack<char>st;
    for(int i=0;i<n;i++) {
        wo[int(code[i]-'a')][curr_hash].push_back(i);
        chash[i] = curr_hash;
        if(st.empty()) {
            st.push(code[i]);
            curr_hash += (int(code[i]-'a' + 1) * power[st.size()]) % hashmod;
            curr_hash %= hashmod;
        }
        else {
            if(st.top() == code[i]) {
                curr_hash += hashmod;
                curr_hash -= (int(st.top()-'a' + 1) * power[st.size()]) % hashmod;
                curr_hash += hashmod;
                curr_hash %= hashmod;
                st.pop();
            }
            else {
                st.push(code[i]);
                curr_hash += (int(code[i]-'a' + 1) * power[st.size()]) % hashmod;
                curr_hash %= hashmod;
            }
        }
        wi[int(code[i]-'a')][curr_hash].push_back(i);
    }
    solve();
    cout<<seq<<"\n";
    return 0;
}

Compilation message (stderr)

match.cpp: In function 'bool check()':
match.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<code.length();i++) {
                 ~^~~~~~~~~~~~~~
match.cpp: In function 'long long int bin_search(int, long long int, int)':
match.cpp:28:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(index+cekor < wi[bukva][ch].size() && wi[bukva][ch][index+cekor] <= value) index+=cekor;
               ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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