Submission #600145

#	Time	Username	Problem	Language	Result	Execution time	Memory
600145		Lucpp	Rail (IOI14_rail)	C++17	100 / 100	79 ms	884 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

void findLocation(int n, int first, int location[], int stype[]){
    stype[0] = 1;
    location[0] = first;
    vector<pair<int, int>> dist0;
    vector<int> di0(n), di1(n);
    for(int i = 1; i < n; i++){
        int d = getDistance(0, i);
        di0[i] = d;
        dist0.emplace_back(d, i);
    }
    sort(dist0.begin(), dist0.end());
    int s = dist0[0].second;
    stype[s] = 2;
    location[s] = first+dist0[0].first;
    for(int i = 1; i < n; i++){
        if(i != s) di1[i] = getDistance(s, i);
    }
    map<int, int> C, D;
    C.emplace(first, 0);
    D.emplace(location[dist0[0].second], dist0[0].second);
    for(int i = 1; i < n-1; i++){
        auto [d0, ind] = dist0[i];
        if(di0[ind] == di0[s] + di1[ind]){
            if(di1[ind] < di0[s]){
                stype[ind] = 1;
                location[ind] = location[s]-di1[ind];
                C.emplace(location[ind], ind);
            }
            else{
                int dc = getDistance(C.begin()->second, ind);
                int lc = C.begin()->first;
                int p = (location[s]-di1[ind] + lc+dc) / 2;
                if(C.count(p)){
                    stype[ind] = 2;
                    location[ind] = lc+dc;
                    D.emplace(location[ind], ind);
                }
                else{
                    stype[ind] = 1;
                    location[ind] = location[s]-di1[ind];
                    C.emplace(location[ind], ind);
                }
            }
        }
        else{
            int dd = getDistance(D.rbegin()->second, ind);
            int rd = D.rbegin()->first;
            int p = (rd-dd + first+d0) / 2;
            if(D.count(p)){
                stype[ind] = 1;
                location[ind] = rd-dd;
                C.emplace(location[ind], ind);
            }
            else{
                stype[ind] = 2;
                location[ind] = first+d0;
                D.emplace(location[ind], ind);
            }
        }
    }
}

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