Submission #153974

#	Time	Username	Problem	Language	Result	Execution time	Memory
153974		popovicirobert	Rail (IOI14_rail)	C++14	30 / 100	272 ms	1648 KiB

rail

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

using namespace std;

static vector <int> loc, type;

int get(int x, int y, int tx, int ty, int n) {
    if(x > y) {
        swap(x, y);
        swap(tx, ty);
    }
    if(tx == 1 && ty == 2) {
        return y - x;
    }

    if(tx == 1 && ty == 1) {
        int mn = 1e9;
        for(int i = 0; i < n; i++) {
            if(type[i] == 2 && loc[i] >= y) {
                mn = min(mn, loc[i]);
            }
        }
        return mn - x + get(y, mn, ty, 2, n);
    }

    int mx = -1;
    for(int i = 0; i < n; i++) {
        if(type[i] == 1 && loc[i] <= x) {
            mx = max(mx, loc[i]);
        }
    }
    return x - mx + get(mx, y, 1, ty, n);

}

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[]) {

    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;

    loc.resize(n), type.resize(n);
    loc[r] = arr[0].first + first; type[r] = 2;
    loc[0] = first; type[0] = 1;

    for(i = 1; i < arr.size(); i++) {
        int k = arr[i].second;
        int cur = loc[l] + query(l, k);


        //cerr << get(cur, loc[r], 2, 2, n) << " " << query(k, r) << " " << get(cur, loc[0], 2, 1, n) << " " << query(0, k) << "\n" ;

        if(get(cur, loc[r], 2, 2, n) == query(k, r) && get(cur, loc[0], 2, 1, n) == query(0, k)) {
            loc[k] = cur;
            type[k] = 2;
            if(loc[k] > loc[r]) {
                r = k;
            }
        }
        else {
            loc[k] = loc[r] - query(r, k);
            type[k] = 1;
            if(loc[l] > loc[k]) {
                l = k;
            }
        }
    }

    for(i = 0; i < n; i++) {
        location[i] = loc[i];
        stype[i] = type[i];
        //cerr << location[i] << " " << stype[i] << "\n";
    }
}

Compilation message (stderr)

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

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