Submission #297789

#	Time	Username	Problem	Language	Result	Execution time	Memory
297789		juckter	Rail (IOI14_rail)	C++14	100 / 100	153 ms	760 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[]) {
    for(int i = 0; i < N; i++)
        stype[i] = -1;
    location[0] = first;
    stype[0] = 1;

    if(N == 1)
        return;

    int anchor, gap = 1e9;
    for(int i = 1; i < N; i++) {
        di0[i] = getDistance(0, i);
        //cerr << "0 " << i << " " << di0[i] << '\n';
        if(di0[i] < gap) {
            gap = di0[i];
            anchor = i;
        }
    }

    cerr << "anchor = " << anchor << " " << location[anchor] << endl;

    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);
        int D = (di0[R] + ex - di0[sta]) / 2;
        bool upward = true;
        for(int i = 0; i < N; i++) {
            if(stype[i] == 2 && location[i] == location[R] - D) {
                upward = false;
                stype[sta] = 1;
                location[sta] = location[R] - ex;
            }
        }
        if(upward) {
            stype[sta] = 2;
            location[sta] = location[0] + di0[sta];
            R = sta;
        }
    }

    // Find left
    int L = 0;
    //cerr << "LEFT" << endl;
    for(auto p : left) {
        int sta = p.second;
        int ex = getDistance(L, sta);
        int D = (di1[L] + ex - di1[sta]) / 2;
        //cerr << sta << " " << di1[sta] << " " << L << " " << D << endl;
        bool downward = true;
        for(int i = 0; i < N; i++) {
            if(stype[i] == 1 && location[i] == location[L] + D) {
                downward = false;
                stype[sta] = 2;
                location[sta] = location[L] + ex;
            }
        }
        if(downward) {
            stype[sta] = 1;
            location[sta] = location[anchor] - di1[sta];
            L = sta;
        }
    }
    //cerr << "END LEFT" << endl;

    //for(int i = 0; i < N; i++)
    //    cerr << location[i] << " " << stype[i] << '\n';

    return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:27:54: warning: 'anchor' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |     cerr << "anchor = " << anchor << " " << location[anchor] << endl;
      |                                                      ^~~~~~

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