Submission #75108

#	Time	Username	Problem	Language	Result	Execution time	Memory
75108		AdrienVannson	Cultivation (JOI17_cultivation)	C++14	5 / 100	29 ms	724 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
    multiset<int> longueursVides; // Entre deux cellules pleines ou en haut ou en bas

    Colonne ()
    {
        longueursVides.insert(nbLignes);
    }

    inline void appliquerEvenement (const Evenement &evenement)
    {
        /*cerr << "Nouvel evenement: " << evenement.iLigne << " " << evenement.estDebut << endl;

        cerr << "Longueurs: ";
        for (auto l : longueursVides) {
            cerr << l << " ";
        }
        cerr << endl;

        cerr << "Nb recouvrements: ";
        for (auto p : nbRecouvrements) {
            cerr << "(" << p.first << " " << p.second << ") ";
        }
        cerr << endl;*/

        if (evenement.estDebut) {
            nbRecouvrements[evenement.iLigne]++;
        }

        map<int, int>::iterator nbRecouvrementsLigne = nbRecouvrements.find(evenement.iLigne);

        int iDebut = 0;
        if (nbRecouvrementsLigne != nbRecouvrements.begin()) {
            nbRecouvrementsLigne--;
            iDebut = nbRecouvrementsLigne->first + 1;
            nbRecouvrementsLigne++;
        }

        int iFin = nbLignes;
        nbRecouvrementsLigne++;
        if (nbRecouvrementsLigne != nbRecouvrements.end()) {
            iFin = nbRecouvrementsLigne->first;
        }
        nbRecouvrementsLigne--;

        if (evenement.estDebut) {
            if (nbRecouvrementsLigne->second == 1) {
                longueursVides.erase(longueursVides.find(iFin - iDebut)); // Supprime une seule occurence
                longueursVides.insert(evenement.iLigne - iDebut);
                longueursVides.insert(iFin - evenement.iLigne - 1);
            }
        }
        else {
            nbRecouvrementsLigne->second--;

            if (nbRecouvrementsLigne->second == 0) {
                nbRecouvrements.erase(nbRecouvrementsLigne);

                longueursVides.insert(iFin - iDebut);
                longueursVides.erase(longueursVides.find(evenement.iLigne - iDebut));
                longueursVides.erase(longueursVides.find(iFin - evenement.iLigne - 1));
            }
        }
    }

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

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

        return nbRecouvrements.begin()->first;
    }

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

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

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

        if (longueursVides.empty()) {
            return 0;
        }

        return *longueursVides.rbegin();
    }

    inline 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);
    }

    int iColonneMin = +oo;
    int iColonneMax = 0;
    for (int iCellulePleine=0; iCellulePleine<nbCellulesPleines; iCellulePleine++) {
        const pair<int, int> &cellule = cellulesPleines[iCellulePleine];

        iColonneMin = min(cellule.second, iColonneMin);
        iColonneMax = max(cellule.second, iColonneMax);
    }

    set<int> nbDroitesPossibles;
    nbDroitesPossibles.insert(0);

    ll nbEtirementsMin = +oo;

    for (int iCellule1=0; iCellule1<nbCellulesPleines; iCellule1++) {
        const int iColonne1 = cellulesPleines[iCellule1].second;

        nbDroitesPossibles.insert(iColonne1); // Depuis la gauche vers la cellule actuelle
        nbDroitesPossibles.insert(nbColonnes - iColonne1 - 1);
        nbDroitesPossibles.insert(iColonneMin + (nbColonnes - iColonne1 - 1));

        for (int iCellule2=0; iCellule2<nbCellulesPleines; iCellule2++) {
            const int iColonne2 = cellulesPleines[iCellule2].second;

            if (iColonne2 > iColonne1) {
                nbDroitesPossibles.insert(iColonne2 - iColonne1 - 1);
                nbDroitesPossibles.insert(iColonneMin + (iColonne2 - iColonne1 - 1));
            }
        }
    }

    for (int nbDroite : nbDroitesPossibles) {
        const ll nbEtirements = (ll)nbDroite + getNbEtirementsVerticauxMin(nbDroite);
        nbEtirementsMin = min(nbEtirements, nbEtirementsMin);
    }

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


#if 0
    int nbDroite = 0;
    int nbEtirementsVerticauxMin = getNbEtirementsVerticauxMin(nbDroite);

    ll nbEtapesMin = nbEtirementsVerticauxMin;

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

        const int nbEtirements = nbEtirementsVerticauxMin;

        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;

        nbEtirementsVerticauxMin = getNbEtirementsVerticauxMin(nbDroite);

        const ll nbEtapes = (ll)nbEtirementsVerticauxMin + nbDroite;

        nbEtapesMin = min(nbEtapes, nbEtapesMin);
    }

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

    return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:265: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:266:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbCellulesPleines);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:270: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: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20