Submission #612668

#	Time	Username	Problem	Language	Result	Execution time	Memory
612668		snasibov05	Rail (IOI14_rail)	C++14	100 / 100	123 ms	660 KiB

rail

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

using namespace std;

#define oo 1000000000

void findLocation(int n, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;

    vector<int> d0(n);
    for (int i = 1; i < n; ++i) d0[i] = getDistance(0, i);
    vector<bool> visited(n); visited[0] = true;

    if (n == 1) return;

    int mni = -1;
    for (int i = 0; i < n; ++i){
        if (!visited[i] && (mni == -1 || d0[i] < d0[mni])) mni = i;
    }
    location[mni] = location[0] + d0[mni];
    stype[mni] = 2;
    visited[mni] = true;

    int l = 0, r = mni;
    vector<pair<int, int>> c, d;
    c.push_back({-location[l], l});
    d.push_back({location[r], r});
    for (int j = 2; j < n; ++j) {
        int cur = -1;
        for (int i = 0; i < n; ++i){
            if (!visited[i] && (cur == -1 || d0[i] < d0[cur])) cur = i;
        }
        visited[cur] = true;
        int dl = getDistance(l, cur), dr = getDistance(r, cur);

        auto it = upper_bound(d.begin(), d.end(), make_pair(location[r] - dr, cur));
        if (location[r] - dr > location[l] && it != d.end() && 2 * location[it->second] - dl - location[l] == location[r] - dr) {
            stype[cur] = 1;
            location[cur] = location[r] - dr;
            continue;
        }

        it = upper_bound(c.begin(), c.end(), make_pair(-(location[l] + dl), cur));
        if (location[l] + dl < location[r] && it != c.end() && dr - location[r] + 2 * location[it->second] == location[l] + dl) {
            stype[cur] = 2;
            location[cur] = location[l] + dl;
            continue;
        }

        if (d0[cur] == d0[mni] + dr - (location[r] - location[mni])) {
            stype[cur] = 1;
            location[cur] = location[r] - dr;
            c.push_back(make_pair(-location[cur], cur));
            l = cur;
        } else {
            stype[cur] = 2;
            location[cur] = location[l] + dl;
            d.push_back(make_pair(location[cur], cur));
            r = cur;
        }
    }
}

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