Submission #149069

#	Time	Username	Problem	Language	Result	Execution time	Memory
149069		Dopatii (#200)	HicCup (FXCUP4_hiccup)	C++17	100 / 100	46 ms	12280 KiB

hiccup

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

int r[1000005], l[1000005];
string s;
bool solve(int st, int dr, int mij){
    int nr = 0;
    for(int i = dr; i >= st ; --i){
        if(s[i] == 'C'){
            bool ok = solve(l[i] + 1, i - 1, mij);
            if(!ok) return 0;

            i = l[i];
            nr -= mij;
            if(nr < 0) return 0;
        }
        else if(s[i] == '!') ++nr;
    }

    return 1;
}

int HicCup(std::string S) {
    s = S;
	int N = S.size();
    int nrH = 0, nrC = 0;
    for(auto i : S){
        if(i == '!' && (nrH == 0 || nrC == 0)) return -1;
        else if(i == 'H') ++nrH;
        else if(i == 'C'){
            ++nrC;
            if(nrC > nrH) return -1;
        }
    }
    for(int i = 0; i < N - 1 ; ++i)
        if(S[i] == 'H' && S[i + 1] == '!') return -1;
    if(nrH != nrC) return -1;

    for(int i = 0; i < N ; ++i){
        int nr = 0;
        while(i < N && S[i] == 'H') ++nr, ++i;
        if(nr < 2) continue ;

        nr = 0;
        while(i < N && S[i] == 'C') ++nr, ++i;
        if(nr >= 2) return 0;
    }

    stack <int> sto;
    for(int i = 0; i < N ; ++i){
        if(S[i] == 'H') sto.push(i);
        else if(S[i] == 'C'){
            r[sto.top()] = i;
            l[i] = sto.top();
            sto.pop();
        }
    }

    int st = 0, dr = N;
    while(st <= dr){
        int mij = (st + dr) / 2;

        bool ok = solve(0, N - 1, mij);


        if(ok) st = mij + 1;
        else dr = mij - 1;
    }

	return dr;
}

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