Submission #700309

#	Time	Username	Problem	Language	Result	Execution time	Memory
700309		Cyanmond	Rail (IOI14_rail)	C++17	30 / 100	635 ms	98516 KiB

rail

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

void findLocation(int N, int first, int location[], int stype[]) {
    if (N == 1) {
        location[0] = first;
        stype[0] = 1;
        return;
    }

    std::vector<std::vector<int>> dists(N, std::vector<int>(N));
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j < N; ++j) {
            dists[i][j] = getDistance(i, j);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            dists[i][j] = dists[j][i];
        }
    }

    stype[0] = 1;
    location[0] = first;
    int secondR = -1;
    for (int i = 1; i < N; ++i) {
        if (secondR == -1 or dists[0][i] < dists[0][secondR]) {
            secondR = i;
        }
    }
    assert(secondR != -1);
    location[secondR] = location[0] + dists[0][secondR];
    stype[secondR] = 2;
    for (int i = 0; i < N; ++i) {
        if (i == 0 or i == secondR) {
            continue;
        }
        const int a = dists[0][i];
        const int b = dists[secondR][i];
        if (a < b) {
            location[i] = location[0] + a;
            stype[i] = 2;
        } else {
            location[i] = location[secondR] - b;
            stype[i] = 1;
        }
    }

    /*
    for (int i = 0; i < N; ++i) {
        std::cout << stype[i] << ' ' << location[i] << std::endl;
    }
    */
}

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