Submission #236233

#	Time	Username	Problem	Language	Result	Execution time	Memory
236233		Bilyana	Rail (IOI14_rail)	C++17	30 / 100	86 ms	888 KiB

rail

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

using namespace std;

const int MAXN = 5000;
const int MAXA = 1e6;
int dist[MAXN], wh[MAXN];
bool ch[MAXN];
int h[MAXA];

struct cmp {
    bool operator()(int l, int r) {
        return dist[l] < dist[r];
    }
};

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

    sort(wh, wh+n, cmp());
    int l = 0, r = 0;
    location[wh[1]] = first + dist[wh[1]];
    stype[wh[1]] = 2;

    for (int i=2; i<n; i++) {
        h[location[wh[i-1]]] = stype[wh[i-1]];
        if (location[wh[i-1]] < location[l]) {
            l = wh[i-1];
        }
        if (location[wh[i-1]] > location[r]) {
            r = wh[i-1];
        }
        int ld = getDistance(l, wh[i]);
        int rd = getDistance(r, wh[i]);
        //cerr<<wh[i]<<" - "<<l<<' '<<r<<" - "<<location[l]<<' '<<location[r]<<" - "<<ld<<' '<<rd<<endl;

        int temp = location[l] + ld;
        int temp2 = temp - (rd - (location[r] - temp)) / 2;
        int temp3 = temp + (rd - (temp - location[r])) / 2;
        if (temp >= 0 && ((temp2 >= 0 && h[temp2] == 1) || (temp3 && h[temp3] == 1))) {
            //cerr<<1<<endl;
            location[wh[i]] = temp;
            stype[wh[i]] = 2;
            continue;
        }
        temp = location[r] - rd;
        temp2 = temp + (ld - (temp - location[l])) / 2;
        temp3 = temp - (ld - (location[l] - temp)) / 2;
        if (temp >= 0 && ((temp2 >= 0 && h[temp2] == 2) || (temp3 && h[temp3] == 2))) {
            //cerr<<2<<endl;
            location[wh[i]] = temp;
            stype[wh[i]] = 1;
            continue;
        }
    }
}

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