// 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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
