oj.uz

Submission #659663

# Submission time Handle Problem Language Result Execution time Memory
659663 2022-11-18T21:52:31 Z Richem Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 1628 KB 
#include "elephants.h"
#include <vector>
#include <iostream>

using namespace std;

const int MAX_ELEPH = 150042, TAILLE_BLOC = 442;

struct Elephant{
    int id, pos;
};

int quelBloc[MAX_ELEPH];
Elephant bloc[TAILLE_BLOC][TAILLE_BLOC*2];

int nbDansBloc[TAILLE_BLOC] = {0};

int nbRequis[TAILLE_BLOC][TAILLE_BLOC*2];
int finPhotoBloc[TAILLE_BLOC][TAILLE_BLOC*2];

int nbElephant, taillePhoto;
int nbBloc;

vector<Elephant> nouv;
void reconstruire(int type) {
    if(type == 0) {
        for(int idBloc = 0; idBloc < nbBloc; idBloc++) {
            for(int id = 0; id < nbDansBloc[idBloc]; id++) {
                nouv.push_back({bloc[idBloc][id]});
            }
            nbDansBloc[idBloc] = 0;
        }
    }
    
    int curBloc = 0, curPos = 0;

    for(auto cur : nouv) {
        if(nbDansBloc[curBloc] == TAILLE_BLOC) {
            curBloc++;
            curPos = 0;
        }
        bloc[curBloc][curPos] = cur;
        nbDansBloc[curBloc]++;
        quelBloc[cur.id] = curBloc;
        curPos++;
    }
    nouv.clear();
}

void calcBloc(int idBloc) {
    int idFin = nbDansBloc[idBloc]-1;
    int posFin = bloc[idBloc][idFin].pos;

    for(int idCur = idFin; idCur >= 0; idCur--) {
        Elephant cur = bloc[idBloc][idCur];
        nbRequis[idBloc][idCur] = 1;
        finPhotoBloc[idBloc][idCur] = cur.pos + taillePhoto;

        if(cur.pos + taillePhoto < posFin) {
            while(cur.pos + taillePhoto < bloc[idBloc][idFin-1].pos) {
                idFin--;
            }
            nbRequis[idBloc][idCur] = nbRequis[idBloc][idFin] + 1;
            finPhotoBloc[idBloc][idCur] = finPhotoBloc[idBloc][idFin];
        }
    }
}

void recalcul() {
    reconstruire(0);
    for(int idBloc = 0; idBloc < nbBloc; idBloc++) {
        calcBloc(idBloc);
    }
}

void enleve(int idBloc, int idModif) {
    int ouModif = 0;
    for(int id = 0; id < nbDansBloc[idBloc]; id++) {
        if(bloc[idBloc][id].id == idModif) {
            ouModif = id;
        }
    }

    bloc[idBloc][ouModif] = {-1, -1};
    for(; ouModif < nbDansBloc[idBloc]-1; ouModif++) {
        swap(bloc[idBloc][ouModif], bloc[idBloc][ouModif+1]);
    }
    nbDansBloc[idBloc]--;
    calcBloc(idBloc);
}

void ajout(int idBloc, int idModif, int posModif) {
    int idCur = nbDansBloc[idBloc];

    while(1) {
        if(idCur > 0 && bloc[idBloc][idCur-1].pos > posModif) {
            swap(bloc[idBloc][idCur-1], bloc[idBloc][idCur]);
            idCur--;
        }
        else {
            break;
        }
    }

    quelBloc[idModif] = idBloc;
    nbDansBloc[idBloc]++;
    bloc[idBloc][idCur] = {idModif, posModif};
    calcBloc(idBloc);
}


void init(int N, int L, int X[]) {
    nbElephant = N, taillePhoto = L;
    nbBloc = (nbElephant + TAILLE_BLOC - 1) / TAILLE_BLOC;

    for(int cur = 0; cur < nbElephant; cur++) {
        nouv.push_back({cur, X[cur]});
    }
    reconstruire(1);
    recalcul();
}

int nbUpdate = 0;

int update(int i, int y) {
    nbUpdate++;
    enleve(quelBloc[i], i);

    int ouAjout = 0;

    while(ouAjout < nbBloc-1 && bloc[ouAjout+1][0].pos < y) {
        ouAjout++;
    }

    ajout(ouAjout, i, y);

    if(nbUpdate % TAILLE_BLOC == 0) {
        recalcul();
    }

    int rep = 0;

    int idBloc = 0;

    int curId = 0;
    while(idBloc < nbBloc) {
        rep += nbRequis[idBloc][curId];
        int finPhoto = finPhotoBloc[idBloc][curId];

        while(idBloc < nbBloc && bloc[idBloc][nbDansBloc[idBloc]-1].pos <= finPhoto) {
            idBloc++;
        }

        if(idBloc == nbBloc) {
            break;
        }

        int deb = 0, fin = nbDansBloc[idBloc]-1;

        while(deb < fin) {
            int milieu = (deb + fin) / 2;

            if(bloc[idBloc][milieu].pos <= finPhoto) {
                deb = milieu;
            }
            else {
                fin = milieu-1;
            }
        }

        curId = deb;
    }

    return rep;
}

int posDepart[MAX_ELEPH];
void input() {
    cin >> nbElephant >> taillePhoto;

    for(int i = 0; i < nbElephant; i++) {
        cin >> posDepart[i];
    }
}

void print() {
    for(int id = 0; id < nbBloc; id++) {
        for(int ah = 0; ah < nbDansBloc[id]; ah++) {
            cout << bloc[id][ah].id << " " << bloc[id][ah].pos << " " << nbRequis[id][ah] << " " << finPhotoBloc[id][ah] << endl;
        }
    }
}

/*
int main() {
    input();
    init(nbElephant, taillePhoto, posDepart);

    recalcul();

    retu
    while(1) {
        int a,b;
        cin >> a >> b;

        cout << update(a, b) << endl;
    }
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Execution timed out 9082 ms 1628 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Execution timed out 9082 ms 1628 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Execution timed out 9082 ms 1628 KB Time limit exceeded
8 Halted 0 ms 0 KB -