Submission #236206

#	Time	Username	Problem	Language	Result	Execution time	Memory
236206		Bilyana	Rail (IOI14_rail)	C++17	30 / 100	81 ms	760 KiB

rail

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

using namespace std;

const int MAXN = 5000;
int dist[MAXN];
int ldist[MAXN], rdist[MAXN];
int wh[MAXN];
bool ch[MAXN];

struct cmpl {
    bool operator()(int l, int r) {
        return ldist[l] < ldist[r];
    }
};
struct cmpr {
    bool operator()(int l, int r) {
        return rdist[l] < rdist[r];
    }
};

void findLocation(int n, int first, int location[], int stype[])
{
    location[0] = first;
    stype[0] = 1;
    ch[0] = 1;
    for (int i=1; i<n; i++) {
        dist[i] = getDistance(0, i);
        wh[i] = i;
    }

    int mn = dist[1], m = 1;
    for (int i=2; i<n; i++) {
        if (mn > dist[i]) {
            m = i;
            mn = dist[i];
        }
    }
    location[wh[m]] = first + dist[wh[m]];
    stype[wh[m]] = 2;
    ch[wh[m]] = 1;

    for (int i=0; i<n; i++) {
        if (ch[i]) {
            ldist[i] = 1e6;
            rdist[i] = 1e6;
            continue;
        }
        int temp = getDistance(i, m);
        if (temp < dist[i]) {
            ldist[i] = temp;
            rdist[i] = 1e6;
        } else {
            rdist[i] = dist[i];
            ldist[i] = 1e6;
        }
    }

    sort(wh, wh+n, cmpl());
    int last = m;
    for (int i=0; i<n; i++) {
        if (ldist[wh[i]] >= 1e6) {
            break;
        }
        int temp = getDistance(last, wh[i]);
        if (temp >= ldist[wh[i]]) {
            location[wh[i]] = location[m] - ldist[wh[i]];
            stype[wh[i]] = 1;
            ch[wh[i]] = 1;
            last = wh[i];
        } else {
            location[wh[i]] = location[last] + temp;
            stype[wh[i]] = 2;
        }
    }

    sort(wh, wh+n, cmpr());
    last = m;
    for (int i=0; i<n; i++) {
        if (rdist[wh[i]] >= 1e6) {
            break;
        }
        int temp = getDistance(last, wh[i]);
        if (temp >= rdist[wh[i]]) {
            location[wh[i]] = location[0] + rdist[wh[i]];
            stype[wh[i]] = 2;
            ch[wh[i]] = 1;
            last = wh[i];
        } else {
            location[wh[i]] = location[last] - temp;
            stype[wh[i]] = 1;
        }
    }
}

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