Submission #150624

#	Time	Username	Problem	Language	Result	Execution time	Memory
150624		Torat (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	180 ms	12204 KiB

hiccup

#include <bits/stdc++.h>
#include "hiccup.h"
//~ #include "grader.cpp"
using namespace std;

const int N = 1000001;

int n;
string s;
vector <int> h;

bool valid(){
    int o = 0;
    for(auto &i : s){
        o += i == 'H';
        o -= i == 'C';
        if(o < 0) return 0;
    }
    if(o) return 0;
    for(auto &i : s){
        if(i == 'H') o = 0;
        else if(i == 'C') o = 1;
        else if(o == 0) return 0;
    }
    return 1;
}
bool check(int x){
    set <int> positive;
    vector <int> g(n);
    for(int i = n - 1 ; i >= 0 ; i--){
        if(s[i] == '!'){
            g[h[i]]++;
            if(g[h[i]] == 1) positive.insert(h[i]);
        }
        else if(s[i] == 'C'){
            if(g[h[i]] < x) return 0;
            g[h[i]] -= x;
            if(g[h[i]] == 0) positive.erase(h[i]);
            while(positive.size() && *positive.rbegin() > h[i]){
                auto it = --positive.end();
                g[*it] = 0;
                positive.erase(it);
            }
        }
    }
    return 1;
}
int HicCup(std::string S) {
    s = S;
    n = s.size();
    if(!valid() || s == string(n, '!')) return -1;
    h.resize(n);
    h[0] = 1;
    for(int i = 1 ; i < n ; i++){
        h[i] = h[i - 1];
        if(s[i] == 'H') h[i]++;
        else if(s[i] == 'C') h[i]--;
        //~ else v[h[i]].push_back(i);
    }
    int l = 0, r = n;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return l - 1;
}

• Subtask 1: 24 / 24
• Subtask 2: 76 / 76