답안 #71356 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71356	2018-08-24T12:08:51 Z	AdrienVannson	Cultivation (JOI17_cultivation)	C++14	5 / 100	16 ms	944 KB

cultivation

// Sous-tâche 1, 2 & 3

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

using namespace std;

const int oo = 1000*1000*1000;

const int NB_MAX_CELLULES_PLEINES = 300;
const int TAILLE_MAX_GRILLE_DEPART = 2*40;

const int TAILLE_MAX = 2 * TAILLE_MAX_GRILLE_DEPART;
const int NB_MAX_LIGNES = TAILLE_MAX;


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;
            }
            return estDebut;
        }
    };

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

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

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

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

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

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

            int iLigneInvalide = -1;

            for (int iLigne=0; iLigne<NB_MAX_LIGNES; iLigne++) {
                if (iColonne - dernierPlein[iLigne] < nbColonnes) { // Invalide
                    iLigneInvalide = iLigne;
                }

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

        }

        // Mise à jour
        for (int 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);

    if (nbLignes > 40 || nbColonnes > 40) {
        exit(42);
    }

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

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

    int nbEtapesMin = +oo;

    for (int nbEtapesBas=0; nbEtapesBas<TAILLE_MAX_GRILLE_DEPART; nbEtapesBas++) {

        if (getEstPossible(nbEtapesBas, 0)) {
            nbEtapesMin = min(nbEtapesBas, nbEtapesMin);
            continue;
        }

        int debut = 0;
        int fin = TAILLE_MAX_GRILLE_DEPART;

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

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

        if (fin < TAILLE_MAX_GRILLE_DEPART) {
            nbEtapesMin = min(nbEtapesBas+fin, nbEtapesMin);
        }
    }

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

    return 0;
}

Compilation message

cultivation.cpp: In function 'int main()':
cultivation.cpp:102: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:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nbCellulesPleines);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:111: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	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	3 ms	400 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	3 ms	580 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	3 ms	704 KB	Output is correct
11	Correct	3 ms	704 KB	Output is correct
12	Correct	3 ms	704 KB	Output is correct
13	Correct	3 ms	704 KB	Output is correct
14	Correct	2 ms	704 KB	Output is correct
15	Correct	4 ms	704 KB	Output is correct
16	Correct	3 ms	704 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	3 ms	400 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	3 ms	580 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	3 ms	704 KB	Output is correct
11	Correct	3 ms	704 KB	Output is correct
12	Correct	3 ms	704 KB	Output is correct
13	Correct	3 ms	704 KB	Output is correct
14	Correct	2 ms	704 KB	Output is correct
15	Correct	4 ms	704 KB	Output is correct
16	Correct	3 ms	704 KB	Output is correct
17	Correct	7 ms	704 KB	Output is correct
18	Correct	16 ms	704 KB	Output is correct
19	Correct	8 ms	704 KB	Output is correct
20	Correct	7 ms	764 KB	Output is correct
21	Correct	12 ms	776 KB	Output is correct
22	Runtime error	4 ms	944 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	3 ms	400 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	3 ms	580 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	3 ms	704 KB	Output is correct
11	Correct	3 ms	704 KB	Output is correct
12	Correct	3 ms	704 KB	Output is correct
13	Correct	3 ms	704 KB	Output is correct
14	Correct	2 ms	704 KB	Output is correct
15	Correct	4 ms	704 KB	Output is correct
16	Correct	3 ms	704 KB	Output is correct
17	Correct	7 ms	704 KB	Output is correct
18	Correct	16 ms	704 KB	Output is correct
19	Correct	8 ms	704 KB	Output is correct
20	Correct	7 ms	764 KB	Output is correct
21	Correct	12 ms	776 KB	Output is correct
22	Runtime error	4 ms	944 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3 ms	944 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3 ms	944 KB	Execution failed because the return code was nonzero
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	3 ms	400 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	3 ms	580 KB	Output is correct
8	Correct	3 ms	580 KB	Output is correct
9	Correct	3 ms	644 KB	Output is correct
10	Correct	3 ms	704 KB	Output is correct
11	Correct	3 ms	704 KB	Output is correct
12	Correct	3 ms	704 KB	Output is correct
13	Correct	3 ms	704 KB	Output is correct
14	Correct	2 ms	704 KB	Output is correct
15	Correct	4 ms	704 KB	Output is correct
16	Correct	3 ms	704 KB	Output is correct
17	Correct	7 ms	704 KB	Output is correct
18	Correct	16 ms	704 KB	Output is correct
19	Correct	8 ms	704 KB	Output is correct
20	Correct	7 ms	764 KB	Output is correct
21	Correct	12 ms	776 KB	Output is correct
22	Runtime error	4 ms	944 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
23	Halted	0 ms	0 KB	-

답안 #71356

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 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
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 30.0

Subtask #5
0 / 20.0

Subtask #6
0 / 20.0