Submission #1063494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063494		VMaksimoski008	Rail (IOI14_rail)	C++17	100 / 100	50 ms	908 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using Node = array<int, 3>;

int dist[5005][5005];

void findLocation(int N, int first, int location[], int stype[]) {
    map<int, int> mp;
    stype[0] = 1; location[0] = first; mp[first] = 0;

    vector<pair<int, int> > vec;
    for(int i=1; i<N; i++) vec.push_back({ getDistance(0, i), i });
    sort(vec.begin(), vec.end());

    location[vec[0].second] = first + vec[0].first;
    stype[vec[0].second] = 2; mp[location[vec[0].second]] = vec[0].second;
    
    int l=0, r=vec[0].second;
    for(int i=1; i<N; i++) {
        int d1 = getDistance(l, vec[i].second);
        int d2 = getDistance(r, vec[i].second);
        int tm = (location[l] + location[r] + d1 - d2) / 2;
        int type;
        if(mp.count(tm)) type = stype[mp[tm]];
        else type = (tm > first ? 1 : 2);

        if(type == 1) {
            location[vec[i].second] = location[l] + d1;
            if(location[vec[i].second] > location[r]) r = vec[i].second;
        } else {
            location[vec[i].second] = location[r] - d2;
            if(location[vec[i].second] < location[l]) l = vec[i].second;
        }

        stype[vec[i].second] = 3 - type;
        mp[location[vec[i].second]] = vec[i].second;
    }

    stype[0] = 1;
}

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