Submission #428628

#	Time	Username	Problem	Language	Result	Execution time	Memory
428628		JeanBombeur	Rail (IOI14_rail)	C++17	100 / 100	96 ms	4348 KiB

rail

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

const int MAX_BLOCS = (1000 * 1000);

int Type[MAX_BLOCS];

pair <int, int> Dist[MAX_BLOCS];

void findLocation(int nbBlocs, int dep, int AnsPosition[], int AnsType[]) {
    
    Type[dep] = 1;
    for (int i = 1; i < nbBlocs; i ++)
    {
        Dist[i] = {getDistance(0, i), i};
    }
    sort(Dist + 1, Dist + nbBlocs);
    
    AnsPosition[0] = dep;
    AnsType[0] = 1;
    
    AnsPosition[Dist[1].second] = dep + Dist[1].first;
    Type[AnsPosition[Dist[1].second]] = AnsType[Dist[1].second] = 2;

    int gauche = 0, droite = Dist[1].second;
    
    for (int i = 2; i < nbBlocs; i ++)
    {
        int id = Dist[i].second;
        int lA = getDistance(id, droite), lB = getDistance(id, gauche);
        int mid = (AnsPosition[gauche] + AnsPosition[droite] - lA + lB) / 2;
        if (Type[mid] == 1 || (Type[mid] == 0 && mid > dep))
        {
            AnsPosition[id] = AnsPosition[gauche] + lB;
            Type[AnsPosition[id]] = AnsType[id] = 2;
        }
        if (Type[mid] == 2 || (Type[mid] == 0 && mid < dep))
        {
            AnsPosition[id] = AnsPosition[droite] - lA;
            Type[AnsPosition[id]] = AnsType[id] = 1;
        }
        if (AnsPosition[id] < AnsPosition[gauche])
            gauche = id;
        if (AnsPosition[id] > AnsPosition[droite])
            droite = id;
    }
    return;
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44