Submission #813549

#	Time	Username	Problem	Language	Result	Execution time	Memory
813549		Wael	Rail (IOI14_rail)	C++14	100 / 100	51 ms	860 KiB

rail

#include<bits/stdc++.h>
using namespace std;
#include "rail.h"
#define F first
#define S second
typedef int ll;
int const M = 5e3 + 20;
int Dis[M][M] , a , b;
set<ll>TypeC , TypeD;
 
bool cmp(int x , int  y) {
    return (Dis[b][x] < Dis[b][y]);
}

void findLocation(int n , int first , int location[], int stype[]) {
 
    int MinDis = 1e9;
    location[a] = first;
    stype[a] = 1;
    TypeC.insert(location[a]);
 
    for(int station = 1 ; station < n ; ++station) {
        Dis[a][station] = getDistance(a , station);
        if(Dis[a][station] < MinDis) {
            b = station;
            MinDis = Dis[a][b];
        }
    }
 
    location[b] = location[a] + Dis[a][b];
    stype[b] = 2;
    TypeD.insert(location[b]);
 
    vector<ll>rem;
    for(int station = 1 ; station < n ; ++station) {
        if(station == b) continue;
        Dis[b][station] = getDistance(b , station);
        rem.push_back(station);
    }
    
    sort(rem.begin() , rem.end() , cmp);
 
    int LeftMost = a , RightMost = b;
 
    for(int station : rem) { 
        if(Dis[a][station] != Dis[a][b] + Dis[b][station]) {
            int CurDis = getDistance(RightMost , station);
            int Expect = location[RightMost] - CurDis;
            auto it = TypeD.lower_bound(Expect);
            if(*it - location[a] + *it - Expect == Dis[a][station]) {
                location[station] = Expect;
                stype[station] = 1;
                TypeC.insert(location[station]);
            } else {
                RightMost = station;
                location[RightMost] = location[a] + Dis[a][RightMost];
                stype[RightMost] = 2;
                TypeD.insert(location[RightMost]);
            }
        }
 
        else {
            if(Dis[b][station] < Dis[a][b]) {
                location[station] = location[b] - Dis[b][station];
                stype[station] = 1;
                TypeC.insert(location[station]);
                continue;
            }
            int CurDis = getDistance(LeftMost , station);
            int Expect = location[LeftMost] + CurDis;
            auto it = TypeC.upper_bound(Expect); --it;
            if(location[b] - *it + Expect - *it == Dis[b][station]) {
                location[station] = Expect;
                stype[station] = 2;
                TypeD.insert(location[station]);
            } else {
                LeftMost = station;
                location[LeftMost] = location[b] - Dis[b][LeftMost];
                stype[LeftMost] = 1;
                TypeC.insert(location[LeftMost]);
            }
        }
    }
 
    return;
}
/*
2
8
1 5
1 6
1 7
2 8
1 1
1 2
2 3
2 4
*/

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