Submission #295231

#	Time	Username	Problem	Language	Result	Execution time	Memory
295231		alexandra_udristoiu	Rail (IOI14_rail)	C++14	100 / 100	158 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(x == 966){
            int abc = 0;
        }
        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;
            if(p > loc[0]){
                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;
                    }
                }
            }
            else{
                p = loc[dr] - dist2;
                if(v[i].first != v[1].first + loc[ v[1].second ] - p){
                    type[x] = 2;
                    loc[x] = loc[st] + dist1;
                    if(loc[x] > loc[dr]){
                        dr = x;
                    }
                }
                else{
                    type[x] = 1;
                    loc[x] = loc[dr] - dist2;
                    if(loc[x] < loc[st]){
                        st = x;
                    }
                }
            }
        }
    }
    int abc = 0;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:25:17: warning: unused variable 'abc' [-Wunused-variable]
   25 |             int abc = 0;
      |                 ^~~
rail.cpp:96:9: warning: unused variable 'abc' [-Wunused-variable]
   96 |     int abc = 0;
      |         ^~~

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