Submission #597127

#	Time	Username	Problem	Language	Result	Execution time	Memory
597127		Bench0310	Rail (IOI14_rail)	C++17	100 / 100	119 ms	2508 KiB

rail

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

using namespace std;
typedef long long ll;

void findLocation(int n,int _t,int pos[],int tp[])
{
    for(int i=0;i<n;i++) pos[i]=-1;
    pos[0]=_t;
    tp[0]=1;
    map<array<int,2>,int> dist;
    auto d=[&](int i,int j)->int
    {
        if(i==j) return 0;
        if(dist.find({i,j})!=dist.end()) return dist[{i,j}];
        return (dist[{i,j}]=dist[{j,i}]=getDistance(i,j));
    };
    int x=1;
    for(int i=1;i<n;i++) if(d(0,i)<d(0,x)) x=i;
    pos[x]=pos[0]+d(0,x);
    tp[x]=2;
    vector<int> left,right;
    for(int i=0;i<n;i++)
    {
        if(i==0||i==x) continue;
        if(d(0,x)+d(x,i)>d(0,i)) right.push_back(i);
        else if(d(x,i)<d(x,0))
        {
            pos[i]=pos[x]-d(x,i);
            tp[i]=1;
        }
        else left.push_back(i);
    }
    //process right
    vector<array<int,2>> dtypes;
    dtypes.push_back({pos[x],x});
    int r=x;
    sort(right.begin(),right.end(),[&](int i,int j){return (d(0,i)<d(0,j));});
    for(int i:right)
    {
        int nl=pos[r]-d(r,i);
        int t=(*lower_bound(dtypes.begin(),dtypes.end(),array<int,2>{nl,0}))[1];
        if(d(0,t)+pos[t]-nl==d(0,i))
        {
            pos[i]=nl;
            tp[i]=1;
        }
        else
        {
            pos[i]=pos[0]+d(0,i);
            tp[i]=2;
            r=i;
            dtypes.push_back({pos[i],i});
        }
    }
    //process left
    vector<array<int,2>> ctypes;
    ctypes.push_back({-pos[0],0});
    int l=0;
    sort(left.begin(),left.end(),[&](int i,int j){return (d(x,i)<d(x,j));});
    for(int i:left)
    {
        int nr=pos[l]+d(l,i);
        int t=(*lower_bound(ctypes.begin(),ctypes.end(),array<int,2>{-nr,0}))[1];
        if(d(x,t)+nr-pos[t]==d(x,i))
        {
            pos[i]=nr;
            tp[i]=2;
        }
        else
        {
            pos[i]=pos[x]-d(x,i);
            tp[i]=1;
            l=i;
            ctypes.push_back({-pos[i],i});
        }
    }
}

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