Submission #148471

#	Time	Username	Problem	Language	Result	Execution time	Memory
148471		USA1 (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	241 ms	9200 KiB

hiccup

#include "hiccup.h"
#include <bits/stdc++.h>

using namespace std;

int N;
string S;
vector <int> hv, cv, ov;

bool works (int K)
{
    hv.clear();
    cv.clear();
    ov.clear();

    //cout << S << " " << K << "\n";

    int nq = 0;
    bool popk = false;
    for (int i = 0; i < N; i++)
    {
        //cout << i << endl;
        if (S[i] == 'H')
        {
            hv.push_back(nq++);
            popk = false;
        }
        else if (S[i] == 'C')
        {
            cv.push_back(nq++);
            popk = false;
        }
        else
        {
            if (popk) continue;
            ov.push_back(nq++);
        }

        if (hv.size() > 0 && cv.size() > 0)
        {
            int h = hv.back(), c = cv.back();
            //cout << h << " " << c << " " << K << " " << nq << endl;
            if (c == h + 1 && c + K < nq)
            {
                while (ov.size() > 0 && ov.back() > h)
                    ov.pop_back();
                hv.pop_back();
                cv.pop_back();
                popk = true;
                if (hv.size() > 0 && cv.size() > 0 && cv.back() == hv.back() + 1)
                    popk = false;
                nq = h;
            }
        }
    }
    return (hv.size() + cv.size() + ov.size()) == 0;
}

int HicCup(string NOTS) {
    S = NOTS;
    N = S.length();

    if (!works(0))
        return -1;

    int lo = 0, hi = N;
    while (lo < hi)
    {
        int mid = (lo + hi + 1) / 2;
        if (works (mid))
            lo = mid;
        else
            hi = mid - 1;
    }
	return lo;
}

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