Submission #96903

#	Time	Username	Problem	Language	Result	Execution time	Memory
96903		SecretAgent007	Rail (IOI14_rail)	C++17	100 / 100	177 ms	17992 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
/*
int diste[109][109];

int getDistance(int a, int b){
    return diste[a][b];
}
*/

int memo[5009][5009];

int dist(int a, int b){
    if(memo[a][b]) return memo[a][b];
    return memo[a][b] = getDistance(a,b);
}

void findLocation(int N, int first, int location[], int stype[]){
	stype[0] = 1;
	location[0] = first;
	vector< pair<int, int> > v(0);
	for(int i = 1; i < N; i++){
        v.push_back({dist(0,i), i});
	}
	sort(v.begin(), v.end());
	int second = v[0].second;
	location[second] = first+dist(0,second);
	stype[second] = 2;

    int R = second;
    set< pair<int, int> > r;
    int L = 0;
    set< pair<int, int> > l;
    r.insert(make_pair(location[R], R));
    l.insert(make_pair(location[L], L));
    //cout << L << ' ' << R << endl;
    for(int it = 1; it < N-1; it++){
        int i = v[it].second;
        if(dist(0,i) == dist(0,second)+dist(second,i) && dist(second,i) > dist(0,second)){
            //LEFT
           // cout << "Left " << i << endl;
            int p = location[L]+dist(L,i);
            auto t = lower_bound(l.begin(), l.end(), make_pair(p,0));
            t--;
            auto vale = *t;
            int val = vale.second;
            //cout << p << ' ' << val << endl;
            int d = p-vale.first;
            if(dist(0,second)+dist(second, val)+d == dist(0,i)){
                location[i] = p;
                stype[i] = 2;
            }else{
                stype[i] = 1;
                L = i;
                location[i] = first-(dist(0,i)-2*dist(0,second));
                l.insert(make_pair(location[i],i));
            }
        }else{
            //RIGHT
            //cout << "Right " << i << endl;
            int p = location[R]-dist(R,i);
            //for(auto a : r) cout << a.first << ' ' << a.second << endl;
            auto t = lower_bound(r.begin(), r.end(), make_pair(p,-1));
            auto vale = *t;
            int val = vale.second;
            //cout << p << ' ' << val << endl;
            int d = vale.first-p;
            if(dist(0,i) == dist(0,val)+d){
                location[i] = location[val]-d;
                stype[i] = 1;
            }else{
                R = i;
                stype[i] = 2;
                location[i] = first+dist(0,i);
                r.insert(make_pair(location[i], i));
            }
        }
    }
}
/*
int main(){
    int n;
    cin >> n;
    int first;
    cin >> first;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> diste[i][j];
        }
    }
    int location[n];
    int stype[n];
    for(int i = 0; i < n; i++){
        location[i] = INT_MAX;
        stype[i] = INT_MAX;
    }
    findLocation(n,first, location,stype);
    cout << endl;
    for(int a : location) cout << a << ' ';
    cout << endl;
    for(int a : stype) cout << a << ' ';
    cout << endl;
}
/*
5 4
0 12 4 15 7
12 0 8 3 11
4 8 0 11 3
15 3 11 0 14
7 11 3 14 0
*/

Compilation message (stderr)

rail.cpp:105:1: warning: "/*" within comment [-Wcomment]
 /*

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