Submission #536432

#	Time	Username	Problem	Language	Result	Execution time	Memory
536432		KoD	Rail (IOI14_rail)	C++17	100 / 100	87 ms	844 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using std::vector;
using std::pair;

void findLocation(int N, int first, int location[], int stype[]) {
    vector<pair<int, int>> list(N - 1);
    for (int i = 1; i < N; ++i) {
        list[i - 1] = {getDistance(0, i), i};
    }
    std::sort(list.begin(), list.end());
    location[0] = first;
    stype[0] = 1;
    int L = 0, R = list[0].second;
    location[R] = location[0] + list[0].first;
    stype[R] = 2;
    std::map<int, int> map;
    map[location[L]] = 1;
    map[location[R]] = 2;
    for (int i = 1; i < N - 1; ++i) {
        const auto& [d0, id] = list[i];
        const int dL = getDistance(L, id);
        const int dR = getDistance(R, id);
        const int m = (dL - dR + location[L] + location[R]) / 2;
        if (const auto itr = map.find(m); (itr == map.end() and m > location[0]) or (itr != map.end() and itr->second == 1)) {
            location[id] = location[L] + dL;
            stype[id] = 2;
            if (location[R] < location[id]) {
                R = id;
            }
        } else {
            location[id] = location[R] - dR;
            stype[id] = 1;
            if (location[L] > location[id]) {
                L = id;
            }
        }
        map[location[id]] = stype[id];
    }
}

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