Submission #856634

#	Time	Username	Problem	Language	Result	Execution time	Memory
856634		abcvuitunggio	Rail (IOI14_rail)	C++17	56 / 100	49 ms	860 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
    int d[N],d2[N],mn=1e9,r=-1;
    location[0]=first;
    stype[0]=1;
    for (int i=1;i<N;i++){
        d[i]=getDistance(0,i);
        if (d[i]<mn){
            mn=d[i];
            r=i;
        }
    }
    location[r]=first+mn;
    stype[r]=2;
    d2[0]=mn;
    vector <pair <int, int>> vl,vr;
    for (int i=1;i<N;i++)
        if (i!=r){
            d2[i]=getDistance(r,i);
            if (d[i]==d2[i]+d[r])
                vl.emplace_back(d2[i],i);
            else
                vr.emplace_back(d[i],i);
        }
    sort(vl.begin(),vl.end());
    sort(vr.begin(),vr.end());
    int last=0;
    vector <pair <int, int>> ve;
    for (auto [dist,i]:vl){
        if (ve.empty()){
            location[i]=location[r]-dist;
            stype[i]=1;
            last=i;
            ve.emplace_back(-location[i],i);
            continue;
        }
        int val=getDistance(last,i);
        int pos=ve[lower_bound(ve.begin(),ve.end(),make_pair(-location[last]-val,i))-ve.begin()].second;
        if ((pos==last?val:getDistance(pos,i))+d2[pos]!=dist){
            location[i]=location[r]-dist;
            stype[i]=1;
            last=i;
            ve.emplace_back(-location[i],i);
            continue;
        }
        location[i]=location[last]+val;
        stype[i]=2;
    }
    last=r;
    ve.clear();
    ve.emplace_back(location[r],r);
    for (auto [dist,i]:vr){
        int val=getDistance(last,i);
        int pos=ve[lower_bound(ve.begin(),ve.end(),make_pair(location[last]-val,i))-ve.begin()].second;
        if ((pos==last?val:getDistance(pos,i))+d[pos]!=dist){
            location[i]=first+dist;
            stype[i]=2;
            last=i;
            ve.emplace_back(location[i],i);
            continue;
        }
        location[i]=location[last]-val;
        stype[i]=1;
    }
}

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