#pragma GCC optimize "O3,inline,unroll-loops,omit-frame-pointer"
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <utility>
using namespace std;
using ll = long long;
const int oo = 2*1000*1000*1000 + 42;
const int NB_MAX_CELLULES_PLEINES = 300;
const int NB_MAX_INDEXS = 3*NB_MAX_CELLULES_PLEINES;
const int NB_MAX_EVENEMENTS = 2*NB_MAX_CELLULES_PLEINES;
int nbLignes, nbColonnes;
int nbCellulesPleines;
pair<int, int> cellulesPleines[NB_MAX_CELLULES_PLEINES];
struct Evenement
{
bool estDebut;
uint iColonne;
uint 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;
}
};
Evenement evenements[NB_MAX_EVENEMENTS];
bool getEstPossible (const uint nbBas, const uint nbDroite)
{
int nbEvenements = 0;
set<uint> ensembleLignesUtiles;
for (int iCellulePleine=0; iCellulePleine<nbCellulesPleines; iCellulePleine++) {
const uint iLigne = cellulesPleines[iCellulePleine].first;
const uint iColonne = cellulesPleines[iCellulePleine].second;
evenements[nbEvenements++] = Evenement{true, iColonne, iLigne, iLigne+nbBas+1};
evenements[nbEvenements++] = Evenement{false, iColonne+nbDroite+1, iLigne, iLigne+nbBas+1};
ensembleLignesUtiles.insert(iLigne);
ensembleLignesUtiles.insert(iLigne+nbBas+1);
if (iLigne > 0) {
ensembleLignesUtiles.insert(iLigne-1);
}
}
// Réindexation
map<uint, int> reindexation;
vector<pair<uint, int>> lignesUtiles; // {iLigne, index}
int nouvelIndex = 0;
for (uint iLigne : ensembleLignesUtiles) {
reindexation[iLigne] = nouvelIndex;
lignesUtiles.push_back(make_pair(iLigne, nouvelIndex));
nouvelIndex++;
}
sort(evenements, evenements+nbEvenements);
for (int iEvenement=0; iEvenement<nbEvenements; iEvenement++) {
evenements[iEvenement].iLigneDebut = reindexation[evenements[iEvenement].iLigneDebut];
evenements[iEvenement].iLigneFin = reindexation[evenements[iEvenement].iLigneFin];
}
int nbRecouvrements[NB_MAX_INDEXS];
fill(nbRecouvrements, nbRecouvrements+NB_MAX_INDEXS, 0);
int dernierPlein[NB_MAX_INDEXS];
fill(dernierPlein, dernierPlein+NB_MAX_INDEXS, +oo);
int nbDebutsVus = 0;
for (int iEvenement=0; iEvenement<nbEvenements; iEvenement++) {
const Evenement &evenement = evenements[iEvenement];
const int iColonne = evenement.iColonne;
// Vérification de la validité
if (!evenement.estDebut && nbDebutsVus == nbCellulesPleines) {
uint iLigneInvalide = -1;
bool dernierValide = false;
for (const pair<uint, int> &ligneUtile : lignesUtiles) {
const uint iLigne = ligneUtile.first;
const int index = ligneUtile.second;
if (dernierValide && iLigne-iLigneInvalide-1 >= (uint)nbLignes) {
return true;
}
if (iColonne - dernierPlein[index] < nbColonnes) { // Invalide
iLigneInvalide = iLigne;
dernierValide = false;
}
else {
dernierValide = true;
}
if (iLigne - iLigneInvalide >= (uint)nbLignes) {
return true;
}
}
}
nbDebutsVus += evenement.estDebut;
// Mise à jour
for (uint 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);
for (int iCellule=0; iCellule<nbCellulesPleines; iCellule++) {
int iLigne, iColonne;
scanf("%d %d", &iLigne, &iColonne);
iLigne--, iColonne--;
cellulesPleines[iCellule] = make_pair(iLigne, iColonne);
}
ll nbEtapesMin = +oo;
ll nbBas = 0;
ll nbDroite = 2*nbColonnes;
//int nbIterations = 0;
while (true) {
ll nbBasAvant = nbBas;
ll nbDroiteAvant = nbDroite;
// Augmenter nbBas
ll debut = nbBas - 1;
ll fin = 2*nbLignes;
while (fin-debut > 1) {
const ll milieu = (debut + fin) / 2;
if (getEstPossible(milieu, nbDroite-1)) {
fin = milieu;
}
else {
debut = milieu;
}
}
nbBas = fin;
// Diminuer nbDroite
debut = -1;
fin = nbDroite;
while (fin-debut > 1) {
const ll 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;
}
/*nbIterations++;
cerr << nbIterations << endl;*/
}
printf("%lld\n", nbEtapesMin);
return 0;
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:153: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:154:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &nbCellulesPleines);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:158: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 |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
508 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
672 KB |
Output is correct |
7 |
Correct |
2 ms |
672 KB |
Output is correct |
8 |
Correct |
2 ms |
672 KB |
Output is correct |
9 |
Correct |
2 ms |
672 KB |
Output is correct |
10 |
Correct |
2 ms |
672 KB |
Output is correct |
11 |
Correct |
2 ms |
672 KB |
Output is correct |
12 |
Correct |
2 ms |
672 KB |
Output is correct |
13 |
Correct |
2 ms |
672 KB |
Output is correct |
14 |
Correct |
2 ms |
672 KB |
Output is correct |
15 |
Correct |
2 ms |
672 KB |
Output is correct |
16 |
Correct |
2 ms |
672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
508 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
672 KB |
Output is correct |
7 |
Correct |
2 ms |
672 KB |
Output is correct |
8 |
Correct |
2 ms |
672 KB |
Output is correct |
9 |
Correct |
2 ms |
672 KB |
Output is correct |
10 |
Correct |
2 ms |
672 KB |
Output is correct |
11 |
Correct |
2 ms |
672 KB |
Output is correct |
12 |
Correct |
2 ms |
672 KB |
Output is correct |
13 |
Correct |
2 ms |
672 KB |
Output is correct |
14 |
Correct |
2 ms |
672 KB |
Output is correct |
15 |
Correct |
2 ms |
672 KB |
Output is correct |
16 |
Correct |
2 ms |
672 KB |
Output is correct |
17 |
Correct |
3 ms |
672 KB |
Output is correct |
18 |
Correct |
4 ms |
672 KB |
Output is correct |
19 |
Correct |
4 ms |
672 KB |
Output is correct |
20 |
Correct |
2 ms |
672 KB |
Output is correct |
21 |
Correct |
13 ms |
672 KB |
Output is correct |
22 |
Correct |
11 ms |
672 KB |
Output is correct |
23 |
Correct |
3 ms |
672 KB |
Output is correct |
24 |
Correct |
14 ms |
672 KB |
Output is correct |
25 |
Correct |
11 ms |
672 KB |
Output is correct |
26 |
Correct |
18 ms |
672 KB |
Output is correct |
27 |
Correct |
22 ms |
672 KB |
Output is correct |
28 |
Correct |
17 ms |
672 KB |
Output is correct |
29 |
Correct |
16 ms |
672 KB |
Output is correct |
30 |
Correct |
16 ms |
672 KB |
Output is correct |
31 |
Correct |
15 ms |
672 KB |
Output is correct |
32 |
Correct |
17 ms |
672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
508 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
672 KB |
Output is correct |
7 |
Correct |
2 ms |
672 KB |
Output is correct |
8 |
Correct |
2 ms |
672 KB |
Output is correct |
9 |
Correct |
2 ms |
672 KB |
Output is correct |
10 |
Correct |
2 ms |
672 KB |
Output is correct |
11 |
Correct |
2 ms |
672 KB |
Output is correct |
12 |
Correct |
2 ms |
672 KB |
Output is correct |
13 |
Correct |
2 ms |
672 KB |
Output is correct |
14 |
Correct |
2 ms |
672 KB |
Output is correct |
15 |
Correct |
2 ms |
672 KB |
Output is correct |
16 |
Correct |
2 ms |
672 KB |
Output is correct |
17 |
Correct |
3 ms |
672 KB |
Output is correct |
18 |
Correct |
4 ms |
672 KB |
Output is correct |
19 |
Correct |
4 ms |
672 KB |
Output is correct |
20 |
Correct |
2 ms |
672 KB |
Output is correct |
21 |
Correct |
13 ms |
672 KB |
Output is correct |
22 |
Correct |
11 ms |
672 KB |
Output is correct |
23 |
Correct |
3 ms |
672 KB |
Output is correct |
24 |
Correct |
14 ms |
672 KB |
Output is correct |
25 |
Correct |
11 ms |
672 KB |
Output is correct |
26 |
Correct |
18 ms |
672 KB |
Output is correct |
27 |
Correct |
22 ms |
672 KB |
Output is correct |
28 |
Correct |
17 ms |
672 KB |
Output is correct |
29 |
Correct |
16 ms |
672 KB |
Output is correct |
30 |
Correct |
16 ms |
672 KB |
Output is correct |
31 |
Correct |
15 ms |
672 KB |
Output is correct |
32 |
Correct |
17 ms |
672 KB |
Output is correct |
33 |
Correct |
8 ms |
672 KB |
Output is correct |
34 |
Correct |
388 ms |
672 KB |
Output is correct |
35 |
Correct |
151 ms |
672 KB |
Output is correct |
36 |
Correct |
132 ms |
672 KB |
Output is correct |
37 |
Correct |
129 ms |
672 KB |
Output is correct |
38 |
Correct |
152 ms |
760 KB |
Output is correct |
39 |
Correct |
157 ms |
760 KB |
Output is correct |
40 |
Correct |
137 ms |
760 KB |
Output is correct |
41 |
Correct |
66 ms |
760 KB |
Output is correct |
42 |
Correct |
75 ms |
760 KB |
Output is correct |
43 |
Correct |
115 ms |
760 KB |
Output is correct |
44 |
Correct |
101 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
760 KB |
Output is correct |
2 |
Correct |
25 ms |
760 KB |
Output is correct |
3 |
Correct |
27 ms |
760 KB |
Output is correct |
4 |
Correct |
184 ms |
760 KB |
Output is correct |
5 |
Correct |
29 ms |
760 KB |
Output is correct |
6 |
Correct |
20 ms |
760 KB |
Output is correct |
7 |
Correct |
11 ms |
760 KB |
Output is correct |
8 |
Correct |
89 ms |
760 KB |
Output is correct |
9 |
Correct |
19 ms |
760 KB |
Output is correct |
10 |
Correct |
36 ms |
760 KB |
Output is correct |
11 |
Correct |
20 ms |
760 KB |
Output is correct |
12 |
Correct |
23 ms |
760 KB |
Output is correct |
13 |
Correct |
5 ms |
760 KB |
Output is correct |
14 |
Correct |
14 ms |
760 KB |
Output is correct |
15 |
Correct |
20 ms |
760 KB |
Output is correct |
16 |
Correct |
20 ms |
760 KB |
Output is correct |
17 |
Correct |
23 ms |
760 KB |
Output is correct |
18 |
Correct |
17 ms |
760 KB |
Output is correct |
19 |
Correct |
23 ms |
760 KB |
Output is correct |
20 |
Correct |
628 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
760 KB |
Output is correct |
2 |
Correct |
25 ms |
760 KB |
Output is correct |
3 |
Correct |
27 ms |
760 KB |
Output is correct |
4 |
Correct |
184 ms |
760 KB |
Output is correct |
5 |
Correct |
29 ms |
760 KB |
Output is correct |
6 |
Correct |
20 ms |
760 KB |
Output is correct |
7 |
Correct |
11 ms |
760 KB |
Output is correct |
8 |
Correct |
89 ms |
760 KB |
Output is correct |
9 |
Correct |
19 ms |
760 KB |
Output is correct |
10 |
Correct |
36 ms |
760 KB |
Output is correct |
11 |
Correct |
20 ms |
760 KB |
Output is correct |
12 |
Correct |
23 ms |
760 KB |
Output is correct |
13 |
Correct |
5 ms |
760 KB |
Output is correct |
14 |
Correct |
14 ms |
760 KB |
Output is correct |
15 |
Correct |
20 ms |
760 KB |
Output is correct |
16 |
Correct |
20 ms |
760 KB |
Output is correct |
17 |
Correct |
23 ms |
760 KB |
Output is correct |
18 |
Correct |
17 ms |
760 KB |
Output is correct |
19 |
Correct |
23 ms |
760 KB |
Output is correct |
20 |
Correct |
628 ms |
760 KB |
Output is correct |
21 |
Correct |
333 ms |
760 KB |
Output is correct |
22 |
Correct |
361 ms |
760 KB |
Output is correct |
23 |
Correct |
178 ms |
772 KB |
Output is correct |
24 |
Correct |
532 ms |
772 KB |
Output is correct |
25 |
Correct |
339 ms |
772 KB |
Output is correct |
26 |
Correct |
185 ms |
772 KB |
Output is correct |
27 |
Execution timed out |
2063 ms |
772 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
508 KB |
Output is correct |
4 |
Correct |
2 ms |
512 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
672 KB |
Output is correct |
7 |
Correct |
2 ms |
672 KB |
Output is correct |
8 |
Correct |
2 ms |
672 KB |
Output is correct |
9 |
Correct |
2 ms |
672 KB |
Output is correct |
10 |
Correct |
2 ms |
672 KB |
Output is correct |
11 |
Correct |
2 ms |
672 KB |
Output is correct |
12 |
Correct |
2 ms |
672 KB |
Output is correct |
13 |
Correct |
2 ms |
672 KB |
Output is correct |
14 |
Correct |
2 ms |
672 KB |
Output is correct |
15 |
Correct |
2 ms |
672 KB |
Output is correct |
16 |
Correct |
2 ms |
672 KB |
Output is correct |
17 |
Correct |
3 ms |
672 KB |
Output is correct |
18 |
Correct |
4 ms |
672 KB |
Output is correct |
19 |
Correct |
4 ms |
672 KB |
Output is correct |
20 |
Correct |
2 ms |
672 KB |
Output is correct |
21 |
Correct |
13 ms |
672 KB |
Output is correct |
22 |
Correct |
11 ms |
672 KB |
Output is correct |
23 |
Correct |
3 ms |
672 KB |
Output is correct |
24 |
Correct |
14 ms |
672 KB |
Output is correct |
25 |
Correct |
11 ms |
672 KB |
Output is correct |
26 |
Correct |
18 ms |
672 KB |
Output is correct |
27 |
Correct |
22 ms |
672 KB |
Output is correct |
28 |
Correct |
17 ms |
672 KB |
Output is correct |
29 |
Correct |
16 ms |
672 KB |
Output is correct |
30 |
Correct |
16 ms |
672 KB |
Output is correct |
31 |
Correct |
15 ms |
672 KB |
Output is correct |
32 |
Correct |
17 ms |
672 KB |
Output is correct |
33 |
Correct |
8 ms |
672 KB |
Output is correct |
34 |
Correct |
388 ms |
672 KB |
Output is correct |
35 |
Correct |
151 ms |
672 KB |
Output is correct |
36 |
Correct |
132 ms |
672 KB |
Output is correct |
37 |
Correct |
129 ms |
672 KB |
Output is correct |
38 |
Correct |
152 ms |
760 KB |
Output is correct |
39 |
Correct |
157 ms |
760 KB |
Output is correct |
40 |
Correct |
137 ms |
760 KB |
Output is correct |
41 |
Correct |
66 ms |
760 KB |
Output is correct |
42 |
Correct |
75 ms |
760 KB |
Output is correct |
43 |
Correct |
115 ms |
760 KB |
Output is correct |
44 |
Correct |
101 ms |
760 KB |
Output is correct |
45 |
Correct |
19 ms |
760 KB |
Output is correct |
46 |
Correct |
25 ms |
760 KB |
Output is correct |
47 |
Correct |
27 ms |
760 KB |
Output is correct |
48 |
Correct |
184 ms |
760 KB |
Output is correct |
49 |
Correct |
29 ms |
760 KB |
Output is correct |
50 |
Correct |
20 ms |
760 KB |
Output is correct |
51 |
Correct |
11 ms |
760 KB |
Output is correct |
52 |
Correct |
89 ms |
760 KB |
Output is correct |
53 |
Correct |
19 ms |
760 KB |
Output is correct |
54 |
Correct |
36 ms |
760 KB |
Output is correct |
55 |
Correct |
20 ms |
760 KB |
Output is correct |
56 |
Correct |
23 ms |
760 KB |
Output is correct |
57 |
Correct |
5 ms |
760 KB |
Output is correct |
58 |
Correct |
14 ms |
760 KB |
Output is correct |
59 |
Correct |
20 ms |
760 KB |
Output is correct |
60 |
Correct |
20 ms |
760 KB |
Output is correct |
61 |
Correct |
23 ms |
760 KB |
Output is correct |
62 |
Correct |
17 ms |
760 KB |
Output is correct |
63 |
Correct |
23 ms |
760 KB |
Output is correct |
64 |
Correct |
628 ms |
760 KB |
Output is correct |
65 |
Correct |
333 ms |
760 KB |
Output is correct |
66 |
Correct |
361 ms |
760 KB |
Output is correct |
67 |
Correct |
178 ms |
772 KB |
Output is correct |
68 |
Correct |
532 ms |
772 KB |
Output is correct |
69 |
Correct |
339 ms |
772 KB |
Output is correct |
70 |
Correct |
185 ms |
772 KB |
Output is correct |
71 |
Execution timed out |
2063 ms |
772 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |