Submission #687660

#	Time	Username	Problem	Language	Result	Execution time	Memory
687660		Alcabel	Rail (IOI14_rail)	C++17	100 / 100	85 ms	588 KiB

rail

#include <rail.h>
#include <bits/stdc++.h>
using namespace std;
const int C = 1, D = 2;

void findLocation(int n, int first, int location[], int stype[]) {
    for (int i = 0; i < n; ++i) {
        location[i] = -1, stype[i] = -1;
    }
    location[0] = first, stype[0] = C;
    vector<int> dFirst(n), dNxt(n);
    dFirst[0] = 0;
    for (int i = 1; i < n; ++i) {
        dFirst[i] = getDistance(0, i);
    }
    int nxt = min_element(dFirst.begin() + 1, dFirst.end()) - dFirst.begin();
    location[nxt] = location[0] + dFirst[nxt];
    stype[nxt] = D;
    dNxt[0] = dFirst[nxt], dNxt[nxt] = 0;
    for (int i = 1; i < n; ++i) {
        if (i != nxt) {
            dNxt[i] = getDistance(nxt, i);
        }
    }
    vector<int> left, right, x;
    for (int i = 1; i < n; ++i) {
        if (i != nxt) {
            if (dFirst[i] == dNxt[i] + dFirst[nxt]) {
                left.emplace_back(i);
            } else {
                right.emplace_back(i);
            }
        }
    }
    sort(left.begin(), left.end(), [&](const int& A, const int& B) {
        return dNxt[A] < dNxt[B];
    });
    for (const int& y : left) {
        if (dNxt[y] <= dNxt[0]) {
            location[y] = location[nxt] - dNxt[y];
            stype[y] = C;
        } else if (!x.empty()) {
            bool isC = true;
            int curD = getDistance(y, x.back());
            for (const int& owner : x) {
                if (curD == dNxt[y] - dNxt[owner] + dNxt[x.back()] - dNxt[owner]) {
                    isC = false;
                    location[y] = location[owner] + dNxt[y] - dNxt[owner];
                    stype[y] = D;
                    break;
                }
            }
            if (isC) {
                location[y] = location[nxt] - dNxt[y];
                stype[y] = C;
                x.emplace_back(y);
            }
        } else {
            location[y] = location[nxt] - dNxt[y];
            stype[y] = C;
            x.emplace_back(y);
        }
    }
    sort(right.begin(), right.end(), [&](const int& A, const int& B) {
        return dFirst[A] < dFirst[B];
    });
    x.clear();
    for (const int& y : right) {
        assert(location[y] == -1);
        if (!x.empty()) {
            bool isD = true;
            int curD = getDistance(y, x.back());
            for (const int& owner : x) {
                if (curD == dFirst[y] - dFirst[owner] + dFirst[x.back()] - dFirst[owner]) {
                    isD = false;
                    location[y] = location[owner] - (dFirst[y] - dFirst[owner]);
                    stype[y] = C;
                    break;
                }
            }
            if (isD) {
                location[y] = location[0] + dFirst[y];
                stype[y] = D;
                x.emplace_back(y);
            }
        } else {
            location[y] = location[0] + dFirst[y];
            stype[y] = D;
            x.emplace_back(y);
        }
    }
}

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