답안 #71887 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71887	2018-08-25T18:37:24 Z	AdrienVannson	Cultivation (JOI17_cultivation)	C++14	30 / 100	1569 ms	896 KB

cultivation

// 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 = 3*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);

        if (iLigne > 0) {
            indexs.insert(iLigne-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:140: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:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbCellulesPleines);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:145: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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	3 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	4 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	4 ms	556 KB	Output is correct
9	Correct	4 ms	556 KB	Output is correct
10	Correct	4 ms	556 KB	Output is correct
11	Correct	3 ms	556 KB	Output is correct
12	Correct	3 ms	556 KB	Output is correct
13	Correct	3 ms	556 KB	Output is correct
14	Correct	3 ms	556 KB	Output is correct
15	Correct	4 ms	556 KB	Output is correct
16	Correct	3 ms	556 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	3 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	4 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	4 ms	556 KB	Output is correct
9	Correct	4 ms	556 KB	Output is correct
10	Correct	4 ms	556 KB	Output is correct
11	Correct	3 ms	556 KB	Output is correct
12	Correct	3 ms	556 KB	Output is correct
13	Correct	3 ms	556 KB	Output is correct
14	Correct	3 ms	556 KB	Output is correct
15	Correct	4 ms	556 KB	Output is correct
16	Correct	3 ms	556 KB	Output is correct
17	Correct	12 ms	556 KB	Output is correct
18	Correct	36 ms	556 KB	Output is correct
19	Correct	37 ms	604 KB	Output is correct
20	Correct	8 ms	604 KB	Output is correct
21	Correct	148 ms	604 KB	Output is correct
22	Correct	163 ms	620 KB	Output is correct
23	Correct	17 ms	620 KB	Output is correct
24	Correct	227 ms	620 KB	Output is correct
25	Correct	209 ms	748 KB	Output is correct
26	Correct	350 ms	896 KB	Output is correct
27	Correct	394 ms	896 KB	Output is correct
28	Correct	275 ms	896 KB	Output is correct
29	Correct	243 ms	896 KB	Output is correct
30	Correct	279 ms	896 KB	Output is correct
31	Correct	242 ms	896 KB	Output is correct
32	Correct	287 ms	896 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	3 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	4 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	4 ms	556 KB	Output is correct
9	Correct	4 ms	556 KB	Output is correct
10	Correct	4 ms	556 KB	Output is correct
11	Correct	3 ms	556 KB	Output is correct
12	Correct	3 ms	556 KB	Output is correct
13	Correct	3 ms	556 KB	Output is correct
14	Correct	3 ms	556 KB	Output is correct
15	Correct	4 ms	556 KB	Output is correct
16	Correct	3 ms	556 KB	Output is correct
17	Correct	12 ms	556 KB	Output is correct
18	Correct	36 ms	556 KB	Output is correct
19	Correct	37 ms	604 KB	Output is correct
20	Correct	8 ms	604 KB	Output is correct
21	Correct	148 ms	604 KB	Output is correct
22	Correct	163 ms	620 KB	Output is correct
23	Correct	17 ms	620 KB	Output is correct
24	Correct	227 ms	620 KB	Output is correct
25	Correct	209 ms	748 KB	Output is correct
26	Correct	350 ms	896 KB	Output is correct
27	Correct	394 ms	896 KB	Output is correct
28	Correct	275 ms	896 KB	Output is correct
29	Correct	243 ms	896 KB	Output is correct
30	Correct	279 ms	896 KB	Output is correct
31	Correct	242 ms	896 KB	Output is correct
32	Correct	287 ms	896 KB	Output is correct
33	Correct	33 ms	896 KB	Output is correct
34	Correct	1569 ms	896 KB	Output is correct
35	Correct	1041 ms	896 KB	Output is correct
36	Correct	1118 ms	896 KB	Output is correct
37	Correct	1138 ms	896 KB	Output is correct
38	Correct	1352 ms	896 KB	Output is correct
39	Correct	1479 ms	896 KB	Output is correct
40	Correct	1156 ms	896 KB	Output is correct
41	Correct	390 ms	896 KB	Output is correct
42	Correct	387 ms	896 KB	Output is correct
43	Correct	1200 ms	896 KB	Output is correct
44	Correct	896 ms	896 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	896 KB	Output is correct
2	Correct	69 ms	896 KB	Output is correct
3	Correct	83 ms	896 KB	Output is correct
4	Incorrect	25 ms	896 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	896 KB	Output is correct
2	Correct	69 ms	896 KB	Output is correct
3	Correct	83 ms	896 KB	Output is correct
4	Incorrect	25 ms	896 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	2 ms	380 KB	Output is correct
3	Correct	3 ms	444 KB	Output is correct
4	Correct	3 ms	444 KB	Output is correct
5	Correct	4 ms	444 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	4 ms	468 KB	Output is correct
8	Correct	4 ms	556 KB	Output is correct
9	Correct	4 ms	556 KB	Output is correct
10	Correct	4 ms	556 KB	Output is correct
11	Correct	3 ms	556 KB	Output is correct
12	Correct	3 ms	556 KB	Output is correct
13	Correct	3 ms	556 KB	Output is correct
14	Correct	3 ms	556 KB	Output is correct
15	Correct	4 ms	556 KB	Output is correct
16	Correct	3 ms	556 KB	Output is correct
17	Correct	12 ms	556 KB	Output is correct
18	Correct	36 ms	556 KB	Output is correct
19	Correct	37 ms	604 KB	Output is correct
20	Correct	8 ms	604 KB	Output is correct
21	Correct	148 ms	604 KB	Output is correct
22	Correct	163 ms	620 KB	Output is correct
23	Correct	17 ms	620 KB	Output is correct
24	Correct	227 ms	620 KB	Output is correct
25	Correct	209 ms	748 KB	Output is correct
26	Correct	350 ms	896 KB	Output is correct
27	Correct	394 ms	896 KB	Output is correct
28	Correct	275 ms	896 KB	Output is correct
29	Correct	243 ms	896 KB	Output is correct
30	Correct	279 ms	896 KB	Output is correct
31	Correct	242 ms	896 KB	Output is correct
32	Correct	287 ms	896 KB	Output is correct
33	Correct	33 ms	896 KB	Output is correct
34	Correct	1569 ms	896 KB	Output is correct
35	Correct	1041 ms	896 KB	Output is correct
36	Correct	1118 ms	896 KB	Output is correct
37	Correct	1138 ms	896 KB	Output is correct
38	Correct	1352 ms	896 KB	Output is correct
39	Correct	1479 ms	896 KB	Output is correct
40	Correct	1156 ms	896 KB	Output is correct
41	Correct	390 ms	896 KB	Output is correct
42	Correct	387 ms	896 KB	Output is correct
43	Correct	1200 ms	896 KB	Output is correct
44	Correct	896 ms	896 KB	Output is correct
45	Correct	44 ms	896 KB	Output is correct
46	Correct	69 ms	896 KB	Output is correct
47	Correct	83 ms	896 KB	Output is correct
48	Incorrect	25 ms	896 KB	Output isn't correct
49	Halted	0 ms	0 KB	-

답안 #71887

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 30.0

Subtask #5 0 / 20.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0