Submission #297770

#	Time	Username	Problem	Language	Result	Execution time	Memory
297770		juckter	Rail (IOI14_rail)	C++14	8 / 100	88 ms	596 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
int di0[MAXN], di1[MAXN];

void findLocation(int N, int first, int location[], int stype[]) {
    location[0] = first;
    stype[0] = 1;

    if(N == 1)
        return;

    int anchor, gap = 3 * N;
    for(int i = 1; i < N; i++) {
        di0[i] = getDistance(0, i);
        if(di0[i] < gap) {
            gap = di0[i];
            anchor = i;
        }
    }

    di1[0] = gap;
    location[anchor] = first + gap;
    stype[anchor] = 2;

    for(int i = 1; i < N; i++) {
        if(i == anchor)
            continue;
        di1[i] = getDistance(anchor, i);
    }


    vector<pair<int, int>> left, right;

    for(int i = 1; i < N; i++) {
        if(i == anchor)
            continue;

        if(di0[i] == gap + di1[i]) {
            // station is to the left of anchor
            if(di1[i] < gap) {
                // downward station for sure
                location[i] = location[anchor] - di1[i];
                stype[i] = 1;
            }
            else
                left.push_back({di1[i], i});
        }
        else {
            // station is to the right of anchor
            right.push_back({di0[i], i});
        }
    }

    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    // Find right
    int R = anchor;
    for(auto p : right) {
        int sta = p.second;
        int ex = getDistance(R, sta);
        if(di0[sta] != di0[R] + ex) {
            // further upward station
            location[sta] = location[0] + di0[sta];
            stype[sta] = 2;
            sta = R;
        }
        else {
            // downward
            location[sta] = location[R] - ex;
            stype[sta] = 1;
        }
    }

    // Find left
    // Find right
    int L = 0;
    for(auto p : left) {
        int sta = p.second;
        int ex = getDistance(L, sta);
        if(di1[sta] != di1[R] + ex) {
            // further downward station
            location[sta] = location[anchor] - di1[sta];
            stype[sta] = 1;
            sta = L;
        }
        else {
            // upward
            location[sta] = location[R] + ex;
            stype[sta] = 2;
        }
    }

    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:25:14: warning: 'anchor' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |     location[anchor] = first + gap;
      |              ^~~~~~

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