Submission #153929

#	Time	Username	Problem	Language	Result	Execution time	Memory
153929		popovicirobert	Rail (IOI14_rail)	C++14	8 / 100	92 ms	1280 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

static map <pair <int, int>, int> qry;

inline int query(int a, int b) {
    if(a > b) swap(a, b);
    if(qry[{a, b}]) {
        return qry[{a, b}];
    }
    return qry[{a, b}] = getDistance(a, b);
}

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

    vector < pair <int, int> > arr;
    int i, l = 0;
    for(i = 1; i < n; i++) {
        arr.push_back({query(0, i), i});
    }
    sort(arr.begin(), arr.end());
    int r = arr[0].second;

    location[r] = arr[0].first + first;
    stype[r] = 2;

    for(i = 1; i < arr.size(); i++) {
        int k = arr[i].second;
        int dst = location[r] - location[l];

        if(query(l, k) < dst) {
            location[k] = location[l] + query(l, k);
            stype[k] = 2;
            continue;
        }
        if(query(r, k) < dst) {
            location[k] = location[r] - query(r, k);
            stype[k] = 1;
            continue;
        }
        if(query(l, k) < query(r, k)) {
            location[k] = location[l] + query(l, k);
            stype[k] = 2;
            r = k;
        }
        else {
            location[k] = location[r] - query(r, k);
            stype[k] = 1;
            l = k;
        }
    }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 1; i < arr.size(); i++) {
                ~~^~~~~~~~~~~~

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