Submission #1108505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108505		arbor	Rail (IOI14_rail)	C++17	100 / 100	50 ms	1608 KiB

rail

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

using namespace std;
using pii = pair<int, int>;

void findLocation(int n, int first, int location[], int stype[]) {
    unordered_map<int, int> loc;
    unordered_map<int, int> type;
    loc[0] = first;
    type[0] = 1;
    vector<int> dis_0(n);
    vector<pii> order;
    for (int i = 1; i < n; i++) {
        dis_0[i] = getDistance(0, i);
        order.emplace_back(dis_0[i], i);
    }
    sort(order.begin(), order.end());
    // min dis is always nearest D to the right
    int x = order[0].second;
    loc[x] = first + order[0].first;
    type[x] = 2;
    vector<int> dis_x(n);
    dis_x[0] = dis_0[x];
    // split into left of 0, in between 0 and x, right of x
    vector<pii> left, right;
    for (int i = 1; i < n - 1; i++) {
        auto [_, y] = order[i];
        dis_x[y] = getDistance(x, y);
        if (dis_0[y] == dis_0[x] + dis_x[y]) { // left of x
            if (dis_x[y] < dis_x[0]) { // in between
                loc[y] = loc[x] - dis_x[y];
                type[y] = 1;
            } else {
                left.emplace_back(dis_x[y], y);
            }
        } else {
            right.emplace_back(dis_0[y], y);
        }
    }
    unordered_map<int, int> seen;
    sort(right.begin(), right.end());
    int r = x; // rightmost D
    for (auto [_, y] : right) {
        // if y is a C then we should have seen the D used (z) to get to y
        int loc_y = loc[r] - getDistance(r, y);
        int loc_z = (loc[0] + loc_y + dis_0[y]) / 2;
        if (seen.count(loc_z) && type[seen[loc_z]] == 2) {
            loc[y] = loc_y;
            type[y] = 1;
        } else {
            loc[y] = loc[0] + dis_0[y];
            type[y] = 2;
            r = y;
        }
        seen[loc[y]] = y;
    }
    sort(left.begin(), left.end());
    int l = 0; // leftmost C
    for (auto [_, y] : left) {
        int loc_y = loc[l] + getDistance(l, y);
        int loc_z = (loc[x] + loc_y - dis_x[y]) / 2;
        if (seen.count(loc_z) && type[seen[loc_z]] == 1) {
            loc[y] = loc_y;
            type[y] = 2;
        } else {
            loc[y] = loc[x] - dis_x[y];
            type[y] = 1;
            l = y;
        }
        seen[loc[y]] = y;
    }
    for (auto [i, loc_i] : loc) {
        location[i] = loc_i;
        stype[i] = type[i];
    } 
}

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