Submission #74393

#	Time	Username	Problem	Language	Result	Execution time	Memory
74393		AdrienVannson	Cultivation (JOI17_cultivation)	C++14	0 / 100	550 ms	720 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_INDEXS = 3*NB_MAX_CELLULES_PLEINES;
const int NB_MAX_EVENEMENTS = 2*NB_MAX_CELLULES_PLEINES;


int nbLignes, nbColonnes;

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


struct Evenement
{
    bool estDebut;
    uint iColonne;
    uint iLigneDebut, iLigneFin;

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

Evenement evenements[NB_MAX_EVENEMENTS];

bool getEstPossible (const uint nbBas, const uint nbDroite)
{
    int nbEvenements = 0;
    set<uint> ensembleLignesUtiles;

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

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

        ensembleLignesUtiles.insert(iLigne);
        ensembleLignesUtiles.insert(iLigne+nbBas+1);

        if (iLigne > 0) {
            ensembleLignesUtiles.insert(iLigne-1);
        }
    }

    // Réindexation
    map<uint, int> reindexation;
    vector<pair<uint, int>> lignesUtiles; // {iLigne, index}

    int nouvelIndex = 0;
    for (uint iLigne : ensembleLignesUtiles) {
        reindexation[iLigne] = nouvelIndex;
        lignesUtiles.push_back(make_pair(iLigne, nouvelIndex));

        nouvelIndex++;
    }

    sort(evenements, evenements+nbEvenements);

    for (int iEvenement=0; iEvenement<nbEvenements; iEvenement++) {
        evenements[iEvenement].iLigneDebut = reindexation[evenements[iEvenement].iLigneDebut];
        evenements[iEvenement].iLigneFin = reindexation[evenements[iEvenement].iLigneFin];
    }

    int nbRecouvrements[NB_MAX_INDEXS];
    fill(nbRecouvrements, nbRecouvrements+NB_MAX_INDEXS, 0);

    int dernierPlein[NB_MAX_INDEXS];
    fill(dernierPlein, dernierPlein+NB_MAX_INDEXS, +oo);

    int nbDebutsVus = 0;

    for (const Evenement &evenement : evenements) {
        const int iColonne = evenement.iColonne;

        // Vérification de la validité
        if (!evenement.estDebut && nbDebutsVus == nbCellulesPleines) {

            uint iLigneInvalide = -1;
            bool dernierValide = false;

            for (const pair<uint, int> &ligneUtile : lignesUtiles) {
                const uint iLigne = ligneUtile.first;
                const int index = ligneUtile.second;

                if (dernierValide && iLigne-iLigneInvalide-1 >= (uint)nbLignes) {
                    return true;
                }

                if (iColonne - dernierPlein[index] < nbColonnes) { // Invalide
                    iLigneInvalide = iLigne;
                    dernierValide = false;
                }
                else {
                    dernierValide = true;
                }

                if (iLigne - iLigneInvalide >= (uint)nbLignes) {
                    return true;
                }
            }
        }

        nbDebutsVus += evenement.estDebut;

        // Mise à jour
        for (uint iLigne=evenement.iLigneDebut; iLigne<evenement.iLigneFin; iLigne++) {
            nbRecouvrements[iLigne] += evenement.estDebut ? 1 : -1;

            if (nbRecouvrements[iLigne] == 0) {
                dernierPlein[iLigne] = +oo;
            }
            else if (dernierPlein[iLigne] == +oo) {
                dernierPlein[iLigne] = iColonne;
            }
        }

    }

    return false;
}


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);
    nbDroitesPossibles.insert(iColonneMin + (nbColonnes - iColonneMax - 1));


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

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

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

    ll nbEtapesMin = +oo;

    for (ll nbDroite : nbDroitesPossibles) {
        // Trouver nbBas
        ll debut = -1;
        ll fin = 2*nbLignes;

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

            if (getEstPossible(milieu, nbDroite)) {
                fin = milieu;
            }
            else {
                debut = milieu;
            }
        }
        const ll nbBas = fin;

        const ll nbEtapes = nbDroite + nbBas;

        nbEtapesMin = min(nbEtapes, nbEtapesMin);
    }

#if 0
    while (true) {

        ll nbBasAvant = nbBas;
        ll nbDroiteAvant = nbDroite;

        // Augmenter nbBas
        ll debut = nbBas - 1;
        ll fin = 2*nbLignes;

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

            if (getEstPossible(milieu, nbDroite-1)) {
                fin = milieu;
            }
            else {
                debut = milieu;
            }
        }
        nbBas = fin;

        // Diminuer nbDroite
        debut = -1;
        fin = nbDroite;

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

            if (getEstPossible(nbBas, milieu)) {
                fin = milieu;
            }
            else {
                debut = milieu;
            }
        }
        nbDroite = fin;


        nbEtapesMin = min(nbBas+nbDroite, nbEtapesMin);

        if ((nbBas == nbBasAvant && nbDroite == nbDroiteAvant) || nbDroite == 0) {
            break;
        }

        /*nbIterations++;
        cerr << nbIterations << endl;*/
    }
#endif

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

    return 0;
}

Compilation message (stderr)

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