// Sous-tâche 1, 2 & 3
#include <algorithm>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <array>
#include <vector>
using namespace std;
const int oo = 2*1000*1000*1000 + 42;
const int NB_MAX_CELLULES_PLEINES = 300;
const int TAILLE_MAX_GRILLE_DEPART = 2*40;
const int NB_MAX_LIGNES = 2 * TAILLE_MAX_GRILLE_DEPART + 2;
const int NB_MAX_COLONNES = 1000*1000*1000 + 1;
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;
}
};
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) {
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);
}
/*for (int i=0; i<40; i++) {
for (int j=0; j<40; j++) {
cerr << getEstPossible(i, j) << " ";
}
cerr << endl;
}*/
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 = TAILLE_MAX_GRILLE_DEPART;
while (fin-debut > 1) {
const int milieu = (debut + fin) / 2;
if (getEstPossible(milieu, nbDroite-1)) {
fin = milieu;
}
else {
debut = milieu;
}
}
nbBas = fin;
/*while (nbBas < TAILLE_MAX_GRILLE_DEPART && !getEstPossible(nbBas, nbDroite-1)) {
nbBas++;
}*/
//cerr << nbBas << " " << nbDroite << endl;
// 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;
/*while (nbDroite > 0 && getEstPossible(nbBas, nbDroite-1)) {
nbDroite--;
}*/
cerr << nbBas << " " << nbDroite << endl;
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:108: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:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &nbCellulesPleines);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &iLigne, &iColonne);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
488 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
488 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
