Submission #426367

#	Time	Username	Problem	Language	Result	Execution time	Memory
426367		JeanBombeur	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	8833 ms	8552 KiB

elephants

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include "elephants.h"
using namespace std;

const int INFINI = (1000 * 1000 * 1000 + 1);
const int MAX_ELEPHANTS = (150 * 1000);
const int LOG = (11);
const int SQRT = (2000);

int Positions[MAX_ELEPHANTS];

vector <int> Elephants[SQRT];

vector <pair <int, int>> Answer[SQRT];

int nbElephants, tailleIntervalle;

void UpdateBucket(int bucket) {
    int sz = Elephants[bucket].size();
    int droite = sz;
    for (int i = droite - 1; i >= 0; i --)
    {
        while (Elephants[bucket][droite - 1] > Elephants[bucket][i] + tailleIntervalle)
            droite --;
        if (droite == sz)
            Answer[bucket][i] = {1, Elephants[bucket][i] + tailleIntervalle};
        else
            Answer[bucket][i] = {1 + Answer[bucket][droite].first, Answer[bucket][droite].second};
    }
    return;
}

void Insert(int bucket, int val) {
    vector <int> nv;
    for (int a : Elephants[bucket])
    {
        if (a >= val)
        {
            nv.push_back(val);
            val = INFINI;
        }
        nv.push_back(a);
    }
    if (val < INFINI)
        nv.push_back(val);
    Elephants[bucket] = nv;
    Answer[bucket].push_back({0, 0});
    UpdateBucket(bucket);
    return;
}

void Remove(int bucket, int val) {
    vector <int> nv;
    for (int a : Elephants[bucket])
    {
        if (a == val)
            val = -1;
        else
            nv.push_back(a);
    }
    Elephants[bucket] = nv;
    UpdateBucket(bucket);
    return;
}

int FindNext(int bucket, int val) {
    int ans = -1;
    int sz = Elephants[bucket].size();
    for (int i = (1 << LOG); i > 0; i /= 2)
    {
        if (ans + i < sz && Elephants[bucket][ans + i] <= val)
            ans += i;
    }
    return ans + 1;
}

int FindAnswer() {
    int ans = 0;
    int curBucket = 0;
    int curId = 0;
    while (Elephants[curBucket].size() > 0)
    {
        ans += Answer[curBucket][curId].first;
        int saut = Answer[curBucket][curId].second;
        curId = FindNext(++ curBucket, saut);
        while (curId != 0 && curId == (int)Elephants[curBucket].size())
            curId = FindNext(++ curBucket, saut);
    }
    return ans;
}

void ResetBuckets() {
    vector <int> AllPos;
    int curBucket = 0;
    while (Elephants[curBucket].size() > 0)
    {
        for (int a : Elephants[curBucket])
            AllPos.push_back(a);
        curBucket ++;
    }
    for (int i = 0; i < curBucket; i ++)
    {
        Elephants[i].clear();
        Answer[i].clear();
    }
    curBucket = 0;
    for (int i = 0; i < nbElephants; i ++)
    {
        if ((int)Elephants[curBucket].size() > SQRT && (nbElephants - i) >= SQRT / 2)
            curBucket ++;
        Elephants[curBucket].push_back(AllPos[i]);
        Answer[curBucket].push_back({0, 0});
    }
    for (int i = 0; i <= curBucket; i ++)
    {
        UpdateBucket(i);
    }
    return;
}

void init(int N, int L, int X[]) {
    nbElephants = N;
    tailleIntervalle = L;
    for (int i = 0; i < nbElephants; i ++)
    {
        Positions[i] = X[i];
    }
    sort(X, X + nbElephants);
    int curBucket = 0;
    for (int i = 0; i < nbElephants; i ++)
    {
        if ((int)Elephants[curBucket].size() > SQRT && (nbElephants - i) >= SQRT / 2)
            curBucket ++;
        Elephants[curBucket].push_back(X[i]);
        Answer[curBucket].push_back({0, 0});
    }
    for (int i = 0; i <= curBucket; i ++)
    {
        UpdateBucket(i);
    }
    return;
}

int update(int id, int nouvPos) {
    
    int prev = Positions[id];
    Positions[id] = nouvPos;
    
    int curBucket = 0;
    bool reset = false;
    while ((int)Elephants[curBucket].size() > 0 && Elephants[curBucket].back() < prev)
        curBucket ++;
    if (Elephants[curBucket].size() == 0)
        curBucket --;
    Remove(curBucket, prev);
    if (Elephants[curBucket].size() == 1)
        reset = true;
    
    curBucket = 0;
    while ((int)Elephants[curBucket].size() > 0 && Elephants[curBucket].back() < nouvPos)
        curBucket ++;
    if (Elephants[curBucket].size() == 0)
        curBucket --;
    Insert(curBucket, nouvPos);
    if (Elephants[curBucket].size() >= 2 * SQRT)
        reset = true;
    
    if (reset)
        ResetBuckets();
    
    return FindAnswer();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3