oj.uz

Submission #426360

# Submission time Handle Problem Language Result Execution time Memory
426360 2021-06-13T20:00:23 Z JeanBombeur Dancing Elephants (IOI11_elephants) C++17
97 / 100
 5728 ms 13564 KB 
#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 SQRT = (400);

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 << 8); 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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 435 ms 1572 KB Output is correct
8 Correct 507 ms 2908 KB Output is correct
9 Correct 720 ms 4628 KB Output is correct
10 Correct 747 ms 3876 KB Output is correct
11 Correct 744 ms 3888 KB Output is correct
12 Correct 940 ms 4100 KB Output is correct
13 Correct 749 ms 3664 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 435 ms 1572 KB Output is correct
8 Correct 507 ms 2908 KB Output is correct
9 Correct 720 ms 4628 KB Output is correct
10 Correct 747 ms 3876 KB Output is correct
11 Correct 744 ms 3888 KB Output is correct
12 Correct 940 ms 4100 KB Output is correct
13 Correct 749 ms 3664 KB Output is correct
14 Correct 615 ms 3492 KB Output is correct
15 Correct 772 ms 3988 KB Output is correct
16 Correct 1385 ms 5116 KB Output is correct
17 Correct 1569 ms 6920 KB Output is correct
18 Correct 1612 ms 6828 KB Output is correct
19 Correct 1408 ms 5832 KB Output is correct
20 Correct 1604 ms 6864 KB Output is correct
21 Correct 1519 ms 5996 KB Output is correct
22 Correct 1178 ms 5268 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 435 ms 1572 KB Output is correct
8 Correct 507 ms 2908 KB Output is correct
9 Correct 720 ms 4628 KB Output is correct
10 Correct 747 ms 3876 KB Output is correct
11 Correct 744 ms 3888 KB Output is correct
12 Correct 940 ms 4100 KB Output is correct
13 Correct 749 ms 3664 KB Output is correct
14 Correct 615 ms 3492 KB Output is correct
15 Correct 772 ms 3988 KB Output is correct
16 Correct 1385 ms 5116 KB Output is correct
17 Correct 1569 ms 6920 KB Output is correct
18 Correct 1612 ms 6828 KB Output is correct
19 Correct 1408 ms 5832 KB Output is correct
20 Correct 1604 ms 6864 KB Output is correct
21 Correct 1519 ms 5996 KB Output is correct
22 Correct 1178 ms 5268 KB Output is correct
23 Correct 4931 ms 13560 KB Output is correct
24 Correct 5333 ms 13500 KB Output is correct
25 Correct 4679 ms 13564 KB Output is correct
26 Correct 5728 ms 12276 KB Output is correct
27 Correct 5665 ms 12212 KB Output is correct
28 Incorrect 49 ms 5048 KB Output isn't correct
29 Halted 0 ms 0 KB -