Submission #236246

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

rail

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

using namespace std;

const int MAXN = 5000 + 100;
const int MAXA = 2e6 + 100;
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, temp2;
        temp = location[l] + ld;
        if (temp < location[r]) {
            temp2 = temp - (rd - (location[r] - temp)) / 2;
            if (temp2 >= 0 && h[temp2] == 1) {
                location[wh[i]] = temp;
                stype[wh[i]] = 2;
            }
        }  else {
            temp2 = location[r] - (rd - (temp - location[r])) / 2;
            if (temp2 >= 0 && h[temp2] == 1) {
                location[wh[i]] = temp;
                stype[wh[i]] = 2;
            }
        }

        temp = location[r] - rd;
        if (temp > location[l]) {
            temp2 = temp + (ld - (temp - location[l])) / 2;
            if (temp2 >= 0 && h[temp2] == 2) {
                location[wh[i]] = temp;
                stype[wh[i]] = 1;
            }
        }  else {
            temp2 = location[l] + (ld - (location[l] - temp)) / 2;
            if (temp > 0 && temp2 >= 0 && h[temp2] == 2) {
                location[wh[i]] = temp;
                stype[wh[i]] = 1;
            }
        }
    }
}

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