Submission #852858

#	Time	Username	Problem	Language	Result	Execution time	Memory
852858		abcvuitunggio	Rail (IOI14_rail)	C++17	30 / 100	45 ms	632 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,l=0,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 (d2[i]<d2[0]){
                location[i]=location[r]-d2[i];
                stype[i]=1;
            }
            else{
                if (d2[i]<d[i])
                    vl.emplace_back(d2[i],i);
                else
                    vr.emplace_back(d[i],i);
            }
            if (d2[i]<mn){
                mn=d2[i];
                l=i;
            }
        }
    sort(vl.begin(),vl.end());
    sort(vr.begin(),vr.end());
    int last=0;
    for (auto [dist,i]:vl){
        int val=getDistance(last,i);
        if (val>d2[last]){
            location[i]=location[r]-d2[i];
            stype[i]=1;
            last=i;
            continue;
        }
        location[i]=location[last]+val;
        stype[i]=2;
    }
    last=r;
    int diff=location[l]-first;
    for (auto [dist,i]:vr){
        int val=getDistance(last,i);
        if (val>d[last]-diff){
            location[i]=location[0]+d[i];
            stype[i]=2;
            last=i;
            continue;
        }
        location[i]=location[last]-val;
        stype[i]=1;
    }
}

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