Submission #1208255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208255		simplemind_31	Rail (IOI14_rail)	C++20	8 / 100	52 ms	35656 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
#define REV(x) x.rbegin(),x.rend()
using namespace std;
int dist[5000][5000];
int ask(int x,int y){
    if(x>y){
        swap(x,y);
    }
    if(dist[x][y]==0){
        dist[x][y]=getDistance(x,y);
    }
    return dist[x][y];
}
void findLocation(int N, int first, int location[], int stype[])
{
    stype[0]=1;
    location[0]=first;
    int mini=1e9,posde,posiz;
    for(int i=1;i<N;i++){
        if(ask(0,i)<mini){
            mini=ask(0,1);
            posde=i;
        }
    }
    location[posde]=first+ask(0,posde);
    stype[posde]=2;
    mini=1e9;
    for(int i=0;i<N;i++){
        if(i==posde){
            continue;
        }
        if(ask(i,posde)<mini){
            mini=ask(i,posde);
            posiz=i;
        }
    }
    stype[posiz]=1;
    location[posiz]=location[posde]-ask(posiz,posde);
    vector<pair<int,int>> derecha,izquierda;
    for(int i=0;i<N;i++){
        if(i==posiz || i==posde){
            continue;
        }
        if(ask(i,posiz)<ask(i,posde)){
            derecha.push_back({ask(i,posiz),i});
        }else{
            izquierda.push_back({ask(i,posde),i});
        }
    }
    sort(ALL(derecha));
    sort(ALL(izquierda));
    int last=posde,most=posiz;
    for(int i=0;i<derecha.size();i++){
        if(ask(last,derecha[i].second)==location[last]-2*location[most]+location[posiz]+derecha[i].first){
            //esta a la derecha
            stype[derecha[i].second]=2;
            location[derecha[i].second]=location[posiz]+derecha[i].first;
            last=derecha[i].second;
        }else{
            stype[derecha[i].second]=1;
            location[derecha[i].second]=location[last]-ask(last,derecha[i].second);
            if(location[derecha[i].second]>location[most]){
                most=derecha[i].second;
            }
        }
    }
    last=posiz;most=posde;
    for(int i=0;i<izquierda.size();i++){
        if(ask(last,izquierda[i].second)==2*location[most]-location[last]-(location[posde]-izquierda[i].first)){
            //esta a la izquierda
            stype[izquierda[i].second]=1;
            location[izquierda[i].second]=location[posde]-izquierda[i].first;
            last=izquierda[i].second;
        }else{
            stype[izquierda[i].second]=2;
            location[izquierda[i].second]=location[last]+ask(last,izquierda[i].second);
            if(location[izquierda[i].second]<location[most]){
                most=izquierda[i].second;
            }
        }
    }
    return;
}

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