Submission #295099

#	Time	Username	Problem	Language	Result	Execution time	Memory
295099		alexandra_udristoiu	Rail (IOI14_rail)	C++14	30 / 100	149 ms	632 KiB

rail

#include "rail.h"
#include<algorithm>
using namespace std;

void findLocation(int n, int frst, int loc[], int type[]){
    int i, st, dr, dist1, dist2, x, j, minim, p;
    pair<int, int> v[5005];
    loc[0] = frst;
    type[0] = 1;
    for(i = 1; i < n; i++){
        v[i].second = i;
        v[i].first = getDistance(0, i);
    }
    sort(v + 1, v + n);
    st = 0;
    dr = v[1].second;
    loc[dr] = v[1].first + loc[0];
    type[dr] = 2;
    for(i = 2; i < n; i++){
        x = v[i].second;
        dist1 = getDistance(st, x);
        dist2 = getDistance(dr, x);
        p = loc[st] + dist1;
        if(p < loc[0]){
            minim = 10000000;
            for(j = 0; j < n; j++){
                if(type[j] == 1){
                    if(loc[j] < p && loc[j] < loc[dr]){
                        minim = min(minim, p - loc[j] + loc[dr] - loc[j]);
                    }
                }
            }
            if(dist2 == minim){
                type[x] = 2;
                loc[x] = p;
                if(loc[x] > loc[dr]){
                    dr = x;
                }
            }
            else{
                type[x] = 1;
                loc[x] = loc[dr] - dist2;
                if(loc[x] < loc[st]){
                    st = x;
                }
            }
        }
        else{
            p = loc[dr] - dist2;
            minim = 10000000;
            for(j = 0; j < n; j++){
                if(type[j] == 2){
                    if(loc[j] > p && loc[j] > loc[st]){
                        minim = min(minim, loc[j] - p + loc[j] - loc[st]);
                    }
                }
            }
            if(minim == dist1){
                type[x] = 1;
                loc[x] = p;
                if(loc[x] < loc[st]){
                    st = x;
                }
            }
            else{
                type[x] = 2;
                loc[x] = loc[st] + dist1;
                if(loc[x] > loc[dr]){
                    dr = x;
                }
            }
        }
    }
}

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