Submission #536420

#	Time	Username	Problem	Language	Result	Execution time	Memory
536420		KoD	Rail (IOI14_rail)	C++17	30 / 100	73 ms	760 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 d = dL - ((dL + dR) - (location[R] - location[L])) / 2;
        if (map[location[L] + d] == 1) {
            location[id] = location[L] + dL;
            stype[id] = 2;
            if (location[id] > location[R]) {
                R = id;
            }
        } else {
            location[id] = location[R] - dR;
            stype[id] = 1;
            if (location[id] < location[L]) {
                L = id;
            }
        }
        map[location[id]] = stype[id];
    }
}

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