Submission #701058

#	Time	Username	Problem	Language	Result	Execution time	Memory
701058		Richem	JJOOII 2 (JOI20_ho_t2)	C++14	100 / 100	73 ms	3172 KiB

ho_t2

#include <iostream>
#include <set>
using namespace std;

const int MAX_TAILLE = 2e5+42, INF = 1e9;

int taille, niveau;
string mot;

int cumul[MAX_TAILLE][3] = {0};

int dicho(int posDeb, int type) {
    int deb = posDeb, fin = taille-1;

    if(posDeb == -1 || cumul[taille][type] - cumul[posDeb][type] < niveau)
        return -1;

    while(deb < fin) {
        int milieu = (deb + fin) / 2;

        if(cumul[milieu+1][type] - cumul[posDeb][type] < niveau) {
            deb = milieu+1;
        }
        else {
            fin = milieu;
        }
    }

    return deb;
}

int main() {
    cin >> taille >> niveau;

    cin >> mot;

    for(int cur = 0; cur < taille; cur++) {
        if(mot[cur] == 'J') 
            cumul[cur+1][0]++;
        else if(mot[cur] == 'O') 
            cumul[cur+1][1]++;
        else
            cumul[cur+1][2]++;

        for(int type = 0; type < 3; type++) {
            cumul[cur+1][type] += cumul[cur][type];
        }
    }

    int rep = INF;

    for(int deb = 0; deb < taille; deb++) {
        int posCur = deb;
        bool bon = 1;

        for(int type = 0; type < 3; type++) {
            posCur = dicho(posCur, type);
            if(posCur == -1) 
                bon = 0;
        }

        if(bon) {
            rep = min(rep, posCur - deb - 3 * niveau + 1);
        }
    }

    if(rep == INF) {
        cout << "-1";
    }
    else {
        cout << rep;
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 12 / 12
• Subtask 3: 87 / 87