Wario Kart II

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

uint32_t *boosts;
uint32_t *position_for_time;
uint32_t max_time = 0;
uint32_t n, k;

float min2f(float a, float b){
        return b < a ? b : a;
}

uint32_t min2(uint32_t a, uint32_t b){
        return b < a ? b : a;
}

uint32_t search(uint32_t obj){
    uint32_t min = obj;
    for(uint32_t i = 0; i <= max_time; i++){
        if(position_for_time[i] + boosts[position_for_time[i]] + k > obj){
            min = min2(min, i + obj - position_for_time[i]);
        } else {
            min = min2(min, i + 1 + obj - position_for_time[i] - boosts[position_for_time[i]]);
        }
    }
    return min;
}

int main() {
    n = 0;
    k = 0;
    if (scanf("%d %d", &n, &k) == 0)
        return EXIT_FAILURE;

    // main algo

    boosts = (uint32_t*) malloc(n * sizeof(uint32_t));

    for (uint32_t i = 0; i < n; i++){
        if (scanf("%d",boosts + i) == 0)
            return EXIT_FAILURE;
    }

    position_for_time = (uint32_t*) calloc(n, sizeof(uint32_t)); //verif
    uint32_t *time_for_position = (uint32_t*) calloc(n, sizeof(uint32_t)); //verif

    for (uint32_t i = 0; i < n; i++){
        uint32_t time = search(i);
        // printf("time : %d, pose = %d\n", time, i);
        position_for_time[time] = i;
        time_for_position[i] = time;
        max_time = max_time > time ? max_time : time;
    }

    float min_time = (float) n;
    float tmp = 0;

    for (uint32_t p = 0; p < n; p++){
        // printf("time : %d, pose = %d\n", time_for_position[p], p);
        if (p + boosts[p] >= n)
            tmp = ((float) time_for_position[p]) + ((float) n - p) / ((float) boosts[p]);
        else
            tmp = ((float) time_for_position[p] + 1 + (n - p - boosts[p]));
        min_time = min2f(min_time, tmp);
    }

    printf("%f\n", min_time);

    return EXIT_SUCCESS;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED