Submission #821721

#	Time	Username	Problem	Language	Result	Execution time	Memory
821721		thimote75	Rail (IOI14_rail)	C++14	100 / 100	52 ms	672 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using bdata = vector<bool>;

template<typename T>
using lpq = priority_queue<T, vector<T>, greater<T>>;
using ii  = pair<int, int>;

idata distance0;

const int DTYPE = 2;
const int CTYPE = 1;

void findLocation(int N, int first, int location[], int stype[])
{
    location[0] = first;
    stype   [0] = 1;
    distance0.resize(N, -1);

    int minD = 1e9;
    int minP = -1;
    for (int i = 1; i < N; i ++) {
        distance0[i] = getDistance(0, i);

        if (distance0[i] >= minD) continue ;
        minD = distance0[i];
        minP = i;
    }

    int lefD = minP;
    int rigD = minP;
    location[minP] = first + minD;
    stype   [minP] = DTYPE;
    int lefC = -1;
    
    lpq<ii> queue;
    for (int i = 1; i < N; i ++)
        if (i != minP)
            queue.push({ distance0[i], i });

    set<int> rigDPos = { first + minD };
    set<int> lefCPos = {  };
    while (queue.size() != 0) {
        const auto nextDP = queue.top(); queue.pop();

        int next = nextDP.second;

        int nextDist = getDistance(lefD, next);
        int offDist  = nextDist + minD;
        int resDist  = distance0[next];

        if (resDist == offDist) {
            bool isLefC = true;
            int passDist;
            if (lefC != -1) {
                passDist = getDistance(lefC, next);
                int potPos = location[lefC] + passDist;

                auto it = lefCPos.lower_bound( potPos ); it --;
                int potLefC = *it;
                int potDist = first + 2 * minD + potPos - 2 * potLefC;

                isLefC = potDist != resDist;
            }

            if (isLefC) {
                lefC = next;
                location[next] = first + minD - nextDist;
                stype   [next] = CTYPE;
                lefCPos.insert( location[next] );
            } else {
                location[next] = passDist + location[lefC];
                stype   [next] = DTYPE;
            }
        } else {
            bool isRigD;

            int passDist = getDistance(rigD, next);
            int potLocat = location[rigD] - passDist;
            int potRigD  = *rigDPos.upper_bound(potLocat);
            int potDist  = 2 * potRigD - potLocat - first;

            isRigD = potDist != resDist;

            if (isRigD) {
                rigD = next;
                location[next] = first + distance0[next];
                stype   [next] = DTYPE;

                rigDPos.insert(location[next]);
            } else {
                location[next] = location[rigD] - passDist;
                stype   [next] = CTYPE;
            }
        }
    }
}

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