Submission #598804

#	Time	Username	Problem	Language	Result	Execution time	Memory
598804		snasibov05	Rail (IOI14_rail)	C++14	30 / 100	294 ms	98636 KiB

rail

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

using namespace std;

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

    vector<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; ++i){
        for (int j = i+1; j < n; ++j) dist[i][j] = dist[j][i] = getDistance(i, j);
    }

    vector<pair<int, int>> d0(n-1);
    for (int i = 1; i < n; ++i) d0[i-1] = {dist[0][i], i};
    sort(d0.begin(), d0.end());

    vector<int> v1, v2;
    for (int i = 0; i < n-1; ++i){
        int dd = d0[i].first;
        int cur = d0[i].second;
        location[cur] = first + dd;
        stype[cur] = 2;
        bool f1 = true, f2 = false;

        for (auto x : v1) {
            if (dist[x][cur] < dd) {
                dd -= dist[0][x];
                location[cur] = location[x] - dd;
                stype[cur] = 1;
                f1 = false;
                break;
            }
        }

        if (location[cur] < first) {
            f2 = true;
            for (auto x : v2) {
                if (dist[x][cur] < dd) {
                    dd = d0[i].first - dist[0][x];
                    location[cur] = location[x] + dd;
                    stype[cur] = 2;
                    f2 = false;
                    break;
                }
            }
        }

        if (f2) v2.push_back(cur);
        else if (f1) v1.push_back(cur);
    }
}

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