Submission #74512

#	Time	Username	Problem	Language	Result	Execution time	Memory
74512		AdrienVannson	Cultivation (JOI17_cultivation)	C++14	60 / 100	2066 ms	768 KiB

cultivation

// #pragma GCC optimize "O3,inline,unroll-loops,omit-frame-pointer"

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <utility>

using namespace std;
using ll = long long;

const int oo = 2*1000*1000*1000 + 42;

const int NB_MAX_CELLULES_PLEINES = 300;

const int NB_MAX_EVENEMENTS = 4*NB_MAX_CELLULES_PLEINES;


int nbLignes, nbColonnes;

int nbCellulesPleines;
pair<int, int> cellulesPleines[NB_MAX_CELLULES_PLEINES];

struct Evenement
{
    bool estDebut;
    bool estPourOuvertureFenetre;
    uint iColonne;
    uint iLigne;

    bool operator< (const Evenement &autre) const
    {
        if (iColonne != autre.iColonne) {
            return iColonne < autre.iColonne;
        }
        if (estDebut != autre.estDebut) {
            return estDebut;
        }
        if (iLigne != autre.iLigne) {
            return iLigne < autre.iLigne;
        }
        return estPourOuvertureFenetre < autre.estPourOuvertureFenetre;
    }
};


const int NB_ETIREMENTS = 3;

const int ETIREMENT_HAUT = 0;
const int ETIREMENT_BAS = 1;
const int ETIREMENT_MILIEU = 2;

struct Colonne
{
    map<int, int> nbRecouvrements; // pour chaque ligne

    Colonne ()
    {}

    void appliquerEvenement (const Evenement &evenement)
    {
        nbRecouvrements[evenement.iLigne] += evenement.estDebut ? 1 : -1;

        if (nbRecouvrements[evenement.iLigne] == 0) {
            nbRecouvrements.erase(evenement.iLigne);
        }
    }

    bool estVide () const
    {
        return nbRecouvrements.empty();
    }

    int nbEtirementsHaut () const
    {
        if (nbRecouvrements.empty()) {
            return +oo;
        }

        return nbRecouvrements.begin()->first;
    }

    int nbEtirementsBas () const
    {
        if (nbRecouvrements.empty()) {
            return +oo;
        }

        return nbLignes - nbRecouvrements.rbegin()->first - 1;
    }

    int nbEtirementsMilieu () const
    {
        if (estVide()) {
            return +oo;
        }

        int nbEtirementsMax = 0;

        int dernierVu = +oo;

        for (const pair<int, int> recouvrement : nbRecouvrements) {
            const int iLigne = recouvrement.first;

            nbEtirementsMax = max(iLigne - dernierVu - 1, nbEtirementsMax);
            dernierVu = iLigne;
        }

        return nbEtirementsMax;
    }

    int nbEtirements (const int iEtirement) const
    {
        if (iEtirement == ETIREMENT_HAUT) {
            return nbEtirementsHaut();
        }
        if (iEtirement == ETIREMENT_BAS) {
            return nbEtirementsBas();
        }
        return nbEtirementsMilieu();
    }
};


Evenement evenements[NB_MAX_EVENEMENTS];

int getNbEtirementsVerticauxMin (const uint nbDroite)
{
    int nbEvenements = 0;

    for (int iCellulePleine=0; iCellulePleine<nbCellulesPleines; iCellulePleine++) {
        const uint iLigne = cellulesPleines[iCellulePleine].first;
        const uint iColonne = cellulesPleines[iCellulePleine].second;

        evenements[nbEvenements++] = Evenement{true, true, iColonne, iLigne};
        evenements[nbEvenements++] = Evenement{false, true, iColonne+nbDroite+1, iLigne};

        evenements[nbEvenements++] = Evenement{true, false, iColonne + nbColonnes, iLigne};
        evenements[nbEvenements++] = Evenement{false, false, iColonne+nbDroite+1 + nbColonnes, iLigne};
    }

    sort(evenements, evenements+nbEvenements);

    int nbEtirementsMin = +oo;

    Colonne debutFenetre;
    Colonne finFenetre;

    int nbColonnesVides = nbColonnes;
    map<int, int> nbOccurencesEtirements[NB_ETIREMENTS];

    for (int iEtirement=0; iEtirement<NB_ETIREMENTS; iEtirement++) {
        nbOccurencesEtirements[iEtirement][+oo] = nbColonnes;
    }

    for (int iEvenement=0; iEvenement<nbEvenements; iEvenement++) {

        // Mettre à jour le meilleur
        if (nbColonnesVides == 0) {
            map<int, int>::iterator it;

            it = nbOccurencesEtirements[ETIREMENT_HAUT].end();
            it--;
            const int nbHaut = it->first;

            it = nbOccurencesEtirements[ETIREMENT_BAS].end();
            it--;
            const int nbBas = it->first;

            it = nbOccurencesEtirements[ETIREMENT_MILIEU].end();
            it--;
            const int nbMilieu = it->first;

            const int nbEtirements = nbHaut + nbBas + max(nbMilieu - nbHaut - nbBas, 0);

            nbEtirementsMin = min(nbEtirements, nbEtirementsMin);
        }


        // Appliquer l'événement
        const Evenement &evenement = evenements[iEvenement];

        if (evenement.estPourOuvertureFenetre) {
            debutFenetre.appliquerEvenement(evenement);
        }
        else {
            finFenetre.appliquerEvenement(evenement);
        }

        // Avancer
        if (iEvenement < nbEvenements-1 && evenements[iEvenement+1].iColonne != evenement.iColonne) {

            const int distAAvancer = evenements[iEvenement+1].iColonne - evenement.iColonne;

            if (debutFenetre.estVide()) {
                nbColonnesVides += distAAvancer;
            }
            if (finFenetre.estVide()) {
                nbColonnesVides -= distAAvancer;
            }

            for (int iEtirement=0; iEtirement<NB_ETIREMENTS; iEtirement++) { // HAUT, BAS, MILIEU
                nbOccurencesEtirements[iEtirement][debutFenetre.nbEtirements(iEtirement)] += distAAvancer;

                nbOccurencesEtirements[iEtirement][finFenetre.nbEtirements(iEtirement)] -= distAAvancer;

                if (nbOccurencesEtirements[iEtirement][finFenetre.nbEtirements(iEtirement)] == 0) {
                    nbOccurencesEtirements[iEtirement].erase(finFenetre.nbEtirements(iEtirement));
                }
            }
        }
    }

    return nbEtirementsMin;
}


int main ()
{
    scanf("%d %d", &nbLignes, &nbColonnes);
    scanf("%d", &nbCellulesPleines);

    for (int iCellule=0; iCellule<nbCellulesPleines; iCellule++) {
        int iLigne, iColonne;
        scanf("%d %d", &iLigne, &iColonne);
        iLigne--, iColonne--;

        cellulesPleines[iCellule] = make_pair(iLigne, iColonne);
    }

    ll nbEtapesMin = getNbEtirementsVerticauxMin(0);

    int nbDroite = 0;

    while (getNbEtirementsVerticauxMin(nbDroite) != getNbEtirementsVerticauxMin(2*nbColonnes)) {

        const int nbEtirements = getNbEtirementsVerticauxMin(nbDroite);

        ll debut = 0;
        ll fin = 2*nbColonnes;

        while (fin - debut > 1) {
            const ll milieu = (debut + fin) / 2;

            if (getNbEtirementsVerticauxMin(milieu) < nbEtirements) {
                fin = milieu;
            }
            else {
                debut = milieu;
            }
        }
        nbDroite = fin;

        const ll nbEtapes = (ll)getNbEtirementsVerticauxMin(nbDroite) + nbDroite;

        nbEtapesMin = min(nbEtapes, nbEtapesMin);
    }

    printf("%lld\n", nbEtapesMin);

    return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:222:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &nbLignes, &nbColonnes);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:223:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbCellulesPleines);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:227:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &iLigne, &iColonne);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20