Submission #674945

#	Time	Username	Problem	Language	Result	Execution time	Memory
674945		bashkort	Rail (IOI14_rail)	C++17	100 / 100	71 ms	716 KiB

rail

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

using namespace std;

void findLocation(int n, int first, int location[], int stype[]) {
    memset(stype, -1, sizeof(stype[0]) * n);

    location[0] = first;
    stype[0] = 1;

    if (n == 1) {
        return;
    }

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

    int p = min_element(dist0.begin() + 1, dist0.end()) - dist0.begin();
    location[p] = first + dist0[p];
    stype[p] = 2;

    for (int i = 0; i < n; ++i) {
        if (i != p) {
            distP[i] = getDistance(i, p);
        }
    }

    vector<pair<int, int>> L, R;
    for (int i = 0; i < n; ++i) {
        if (i != p && (i == 0 || dist0[i] == dist0[p] + distP[i])) {
            L.emplace_back(distP[i], i);
        } else {
            R.emplace_back(dist0[i], i);
        }
    }
    set<int> st;

    sort(L.begin(), L.end());
    int last_c = -1;
    for (auto [x, i]: L) {
        bool c = last_c == -1;

        int dist;
        if (!c) {
            dist = getDistance(last_c, i);
            int kek = (distP[i] + dist - distP[last_c]);
            int cord = location[p] - (distP[i] - kek / 2);
            c = kek % 2 == 0 && !st.count(cord);
        }

        if (c) {
            location[i] = location[p] - distP[i];
            stype[last_c = i] = 1;
            st.insert(location[i]);
        } else {
            location[i] = location[last_c] + dist;
            stype[i] = 2;
        }
    }

    st.clear();

    int last_d = -1;
    sort(R.begin(), R.end());
    for (auto [x, i]: R) {
        int dist;
        bool d = last_d == -1;

        if (!d) {
            dist = getDistance(last_d, i);
            int kek = (dist0[i] + dist - dist0[last_d]);
            int cord = location[0] + (dist0[i] - kek / 2);
            d = kek % 2 == 0 && !st.count(cord);
        }

        if (d) {
            location[i] = location[0] + dist0[i];
            stype[last_d = i] = 2;
            st.insert(location[i]);
        } else {
            location[i] = location[last_d] - dist;
            stype[i] = 1;
        }
    }
}

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