Submission #1273559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273559		Aviansh	Rail (IOI14_rail)	C++20	100 / 100	80 ms	98740 KiB

rail

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

using namespace std;

const int maxn = 5005;

int mem[maxn][maxn];

int dist(int i, int j){
    if(mem[i][j]==-1){
        mem[i][j]=getDistance(i,j);
        mem[j][i]=mem[i][j];
    }
    return mem[i][j];
}

set<int>typc;
set<int>typd;

int basedon1(int x, int r){
    //r->x where r is D, x is D
    auto it = typc.upper_bound(x);
    if(it!=typc.begin()){
        it--;
    }
    else{
        return 1e9;
    }
    return r-(*it)+x-(*it);
}

int basedon2(int x, int f){
    auto it = typd.upper_bound(max(x,f));
    if(it==typd.end()){
        return 1e9;
    }
    return (*it)-x+(*it)-f;
}

void findLocation(int n, int first, int location[], int stype[]) {
    typc.clear();
    typd.clear();
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            mem[i][j]=-1;
        }
    }
    location[0]=first;
    stype[0]=1;
    typc.insert(first);
    //base set
    array<int,2> dist0[n];
    dist0[0]={0,0};
    for(int i = 1;i<n;i++){
        dist0[i]={dist(0,i),i};
    }
    sort(dist0,dist0+n);
    int rig = dist0[1][1];
    int rigd = dist0[1][0];

    location[rig]=first+dist0[1][0];
    typd.insert(first+dist0[1][0]);
    stype[rig]=2;

    int lef = 0;
    int lefd = 0;
    for(int i = 2;i<n;i++){
        int k = dist0[i][1];
        int dr = dist(rig,k);
        int dl = dist(lef,k);
        int d0 = dist(0,k);
        //Case 1:
            int pos = location[lef]+dl;
            if(pos<first){
                if(basedon1(pos,location[rig])==dr){
                    //nice this is good
                    location[k]=pos;
                    stype[k]=2;
                    typd.insert(pos);
                    continue;
                }
            }
        //Case 2:
            pos=location[rig]-dr;
            if(pos>first){
                if(d0==dl-(first-location[lef])){
                    if(basedon2(pos,first)==d0&&basedon2(pos,location[lef])==dl){
                        //valid
                        location[k]=pos;
                        stype[k]=1;
                        typc.insert(pos);
                        continue;
                    }
                }
            }
            else{
                //Case 3:
                if(basedon2(pos,first)==d0){
                    //valid
                    assert(pos<location[lef]);
                    location[k]=pos;
                    stype[k]=1;
                    lef=k;
                    typc.insert(pos);
                    continue;
                }
            }
        //Case 4:
        pos=location[lef]+dl;
        location[k]=pos;
        stype[k]=2;
        assert(pos>location[rig]);
        rig=k;
        typd.insert(pos);
    }
}

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