Submission #166149

#	Time	Username	Problem	Language	Result	Execution time	Memory
166149		tri	Rail (IOI14_rail)	C++14	30 / 100	83 ms	760 KiB

rail

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

int N;

void findLocation(int n, int first, int location[], int stype[]) {
    N = n;

    vi dist0(N);
    dist0[0] = 0;

    for (int i = 1; i < N; i++) {
        dist0[i] = getDistance(0, i);
    }

    int minI = -1;
    for (int i = 1; i < N; i++) {
        if (minI == -1 || dist0[i] < dist0[minI]) {
            minI = i;
        }
    }

    int r = minI; // r is going up

    vi distR(N);
    distR[r] = 0;
    for (int i = 0; i < N; i++) {
        if (i != r) {
            distR[i] = getDistance(i, r);
        }
    }

    minI = -1;
    for (int i = 0; i < N; i++) {
        if (i == r) continue;
        if (minI == -1 || distR[i] < distR[minI]) {
            minI = i;
        }
    }

    int l = minI;

    vi distL(N);
    distL[l] = 0;

    for (int i = 0; i < N; i++) {
        if (i != l) {
            distL[i] = getDistance(i, l);
        }
    }

    vi side(N);

    for (int i = 0; i < N; i++) {
        if (i != l && i != r) {
            if (distL[i] < distR[i]) {
                side[i] = 1;
            } else {
                side[i] = 0;
            }
        }
    }
    side[l] = 0;
    side[r] = 1;

    assert(l == 0);

    for (int i = 0; i < N; i++) {
        if (side[i] == 0) {
            stype[i] = 1;
            location[i] = first + distL[r] - distR[i];
        } else {
            stype[i] = 2;
            location[i] = first + distL[i];
        }
    }
}

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