Submission #1255819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255819		badge881	Rail (IOI14_rail)	C++20	100 / 100	39 ms	608 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
using namespace std;

const int INF = 1e8;

struct Station
{
    int index, dist;
};

int distFrom0[10000], distFromSP[10000];
int stationType[10000];
int coordLeft[10000], coordRight[10000];
int coord[10000];

vector<Station> leftList, rightList;

bool cmpAsc(const Station &a, const Station &b)
{
    return a.dist < b.dist;
}

void findLocation(int n, int firstCoord, int location[], int type[])
{
    // Initialisation de la première station
    location[0] = firstCoord;
    type[0] = 1;
    stationType[0] = 2; // point de référence

    int spIndex = 0;
    int minDist = INF;

    // Trouver la station la plus proche de la station 0
    for (int i = 1; i < n; i++)
    {
        distFrom0[i] = getDistance(0, i);
        if (distFrom0[i] < minDist)
        {
            spIndex = i;
            minDist = distFrom0[i];
        }
    }

    // Placer cette station à droite
    location[spIndex] = firstCoord + distFrom0[spIndex];
    type[spIndex] = 2;
    stationType[spIndex] = 2;

    int cntLeft = 1, cntRight = 1;
    coordLeft[cntLeft] = firstCoord;
    coordRight[cntRight] = location[spIndex];

    // Classer les autres stations en gauche, droite ou indéterminé
    for (int i = 1; i < n; i++)
    {
        if (i == spIndex)
            continue;

        distFromSP[i] = getDistance(spIndex, i);

        if (distFrom0[i] == distFromSP[i] + distFrom0[spIndex])
        {
            if (distFromSP[i] < distFrom0[spIndex])
            {
                stationType[i] = 2; // gauche par rapport à spIndex
                location[i] = location[spIndex] - distFromSP[i];
                type[i] = 1;
                coordLeft[++cntLeft] = location[i];
            }
            else
            {
                stationType[i] = 1;
            }
        }
        else
        {
            stationType[i] = 0;
        }
    }

    // Construire les listes gauche/droite
    for (int i = 1; i < n; i++)
    {
        if (stationType[i] == 1)
            leftList.push_back({i, distFromSP[i]});
        else if (stationType[i] == 0)
            rightList.push_back({i, distFrom0[i]});
    }

    sort(rightList.begin(), rightList.end(), cmpAsc);
    sort(leftList.begin(), leftList.end(), cmpAsc);

    // Placement des stations à droite
    int current = spIndex;
    for (auto &st : rightList)
    {
        int idx = st.index;
        int dist0 = st.dist;

        if (current == spIndex)
        {
            location[idx] = firstCoord + dist0;
            type[idx] = 2;
            current = idx;
            coordRight[++cntRight] = location[idx];
        }
        else
        {
            int dCur = getDistance(current, idx);
            int candCoord = location[current] - dCur;

            int minRight = INF;
            for (int j = 1; j <= cntRight; j++)
                if (coordRight[j] > candCoord)
                    minRight = min(minRight, coordRight[j]);

            if (dist0 == 2 * minRight - candCoord - firstCoord)
            {
                location[idx] = location[current] - dCur;
                type[idx] = 1;
                coordLeft[++cntLeft] = location[idx];
            }
            else
            {
                location[idx] = firstCoord + dist0;
                type[idx] = 2;
                current = idx;
                coordRight[++cntRight] = location[idx];
            }
        }
    }

    current = 0;
    for (auto &st : leftList)
    {
        int idx = st.index;
        int distSP = st.dist;

        if (current == 0)
        {
            location[idx] = location[spIndex] - distSP;
            type[idx] = 1;
            current = idx;
            coordLeft[++cntLeft] = location[idx];
        }
        else
        {
            int dCur = getDistance(current, idx);
            int candCoord = location[current] + dCur;

            int maxLeft = 0;
            for (int j = 1; j <= cntLeft; j++)
                if (coordLeft[j] < candCoord)
                    maxLeft = max(maxLeft, coordLeft[j]);

            if (distSP == candCoord + location[spIndex] - 2 * maxLeft)
            {
                location[idx] = candCoord;
                type[idx] = 2;
                coordRight[++cntRight] = location[idx];
            }
            else
            {
                location[idx] = location[spIndex] - distSP;
                type[idx] = 1;
                current = idx;
                coordLeft[++cntLeft] = location[idx];
            }
        }
    }
}

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