Submission #236221

#	Time	Username	Problem	Language	Result	Execution time	Memory
236221		Bilyana	Rail (IOI14_rail)	C++17	30 / 100	80 ms	504 KiB

rail

#include <bits/stdc++.h>
//#include "grader.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 = wh[0], newlast = wh[0];
    if (ldist[wh[0]] < 1e6) {
        location[wh[0]] = location[m] - ldist[wh[0]];
        stype[wh[0]] = 1;
    }
    for (int i=1; i<n; i++) {
        if (ldist[wh[i]] >= 1e6) {
            break;
        }
        int temp = getDistance(last, wh[i]);
        if (abs(ldist[wh[i]] - abs((location[m] - location[last]))) != temp) {
            location[wh[i]] = location[m] - ldist[wh[i]];
            stype[wh[i]] = 1;
            ch[wh[i]] = 1;
            newlast = wh[i];
            if (i < n && ldist[wh[i+1]] == ldist[wh[i]]) {
                continue;
            }
        } else {
            location[wh[i]] = location[last] + temp;
            stype[wh[i]] = 2;
        }
        last = newlast;
    }

    sort(wh, wh+n, cmpr());
    last = m, newlast = m;
    for (int i=0; i<n; i++) {
        if (rdist[wh[i]] >= 1e6) {
            break;
        }
        int temp = getDistance(last, wh[i]);
        //cerr<<last<<' '<<wh[i]<<' '<<temp<<endl;
        //cerr<<wh[i]<<" - "<<rdist[wh[i]]<<' '<<temp<<" - "<<abs(rdist[wh[i]] - abs((location[m] - location[last])))<<endl;;
        if (abs(rdist[wh[i]] - abs((location[last] - location[0]))) != temp) {
            location[wh[i]] = location[0] + rdist[wh[i]];
            stype[wh[i]] = 2;
            ch[wh[i]] = 1;
            last = wh[i];
            if (i < n && ldist[wh[i+1]] == ldist[wh[i]]) {
                continue;
            }
        } else {
            location[wh[i]] = location[last] - temp;
            stype[wh[i]] = 1;
        }
        //last = newlast;
    }
}

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