oj.uz

답안 #71886

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71886 2018-08-25T18:33:28 Z AdrienVannson Cultivation (JOI17_cultivation) C++14
0 / 100
 20 ms 432 KB 
// Sous-tâche 1, 2, 3 (et plus ?)
// BUG: étirer des 2*NB_MAX_LIGNES (?)

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

using namespace std;

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

const int NB_MAX_CELLULES_PLEINES = 300;

const int NB_MAX_LIGNES = 1000*1000*1000+1;
const int NB_MAX_COLONNES = 1000*1000*1000 + 1;

const int NB_MAX_INDEXS = 2*NB_MAX_CELLULES_PLEINES;


int nbLignes, nbColonnes;

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


bool getEstPossible (const int nbBas, const int nbDroite)
{
    struct Evenement
    {
        bool estDebut;
        int iColonne;
        int 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;
        }
    };

    set<int> indexs;
    vector<Evenement> evenements;

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

        evenements.push_back(Evenement{true, iColonne, iLigne, iLigne+nbBas+1});
        evenements.push_back(Evenement{false, iColonne+nbDroite+1, iLigne, iLigne+nbBas+1});

        indexs.insert(iLigne);
        indexs.insert(iLigne+nbBas+1);
    }

    // Réindexation
    map<int, int> reindexation;

    int nouvelIndex = 0;
    for (int index : indexs) {
        reindexation[index] = nouvelIndex;
        nouvelIndex++;
    }

    sort(evenements.begin(), evenements.end());

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

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

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

        // Vérification de la validité
        if (!evenement.estDebut) {

            int iLigneInvalide = -1;
            bool dernierValide = false;

            for (int iLigne : indexs) {
                const int index = reindexation[iLigne];

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

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

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

        }

        // Mise à jour
        for (int iLigne=reindexation[evenement.iLigneDebut]; iLigne<reindexation[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);
    }

    /*cerr << getEstPossible(3, 3) << endl;
    return 0;*/

    int nbEtapesMin = +oo;
    int nbBas = 0;
    int nbDroite = NB_MAX_COLONNES;

    while (true) {

        int nbBasAvant = nbBas;
        int nbDroiteAvant = nbDroite;

        // Augmenter nbBas
        int debut = -1;
        int fin = NB_MAX_LIGNES;

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

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

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

        while (fin-debut > 1) {
            const int 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;
        }
    }

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

    return 0;
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:136: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:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbCellulesPleines);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:141: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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -