Submission #700770

#	Time	Username	Problem	Language	Result	Execution time	Memory
700770		Forested	Rail (IOI14_rail)	C++17	100 / 100	320 ms	552 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;

#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    } else {
        return false;
    }
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    } else {
        return false;
    }
}

constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;

void findLocation(int n, int first, int location[], int stype[]) {
    Vec<i32> dist_0(n, 0);
    REP(i, 1, n) {
        dist_0[i] = getDistance(0, i);
    }
    i32 y = 0;
    {
        i32 mn = INF;
        REP(i, 1, n) {
            if (chmin(mn, dist_0[i])) {
                y = i;
            }
        }
    }
    
    Vec<i32> dist_y(n, 0);
    dist_y[0] = dist_0[y];
    REP(i, 1, n) {
        if (i != y) {
            dist_y[i] = getDistance(i, y);
        }
    }
    
    stype[0] = 1;
    location[0] = first;
    stype[y] = 2;
    location[y] = first + dist_0[y];
    
    {
        Vec<i32> idx;
        REP(i, n) {
            if (i == 0 || (i != y && dist_y[i] + dist_0[y] == dist_0[i])) {
                idx.push_back(i);
            }
        }
        sort(ALL(idx), [&](i32 i, i32 j) -> bool {
            return dist_y[i] < dist_y[j];
        });
        i32 last = -1;
        bool seen_0 = false;
        Vec<i32> ones;
        for (i32 i : idx) {
            if (!seen_0) {
                location[i] = location[y] - dist_y[i];
                stype[i] = 1;
                last = i;
                ones.push_back(location[i]);
                if (i == 0) {
                    seen_0 = true;
                }
                continue;
            }
            i32 d = getDistance(i, last);
            i32 ph = location[last] + d;
            if (ph >= location[0]) {
                location[i] = location[y] - dist_y[i];
                stype[i] = 1;
                last = i;
                ones.push_back(location[i]);
                continue;
            }
            i32 mx = -INF;
            for (i32 pos : ones) {
                if (pos < ph) {
                    chmax(mx, pos);
                }
            }
            if (ph - mx + location[y] - mx == dist_y[i]) {
                location[i] = ph;
                stype[i] = 2;
            } else {
                location[i] = location[y] - dist_y[i];
                stype[i] = 1;
                last = i;
                ones.push_back(location[i]);
            }
        }
    }
    {
        Vec<i32> idx;
        REP(i, n) {
            if (i != 0 && i != y && dist_y[i] + dist_y[0] != dist_0[i]) {
                idx.push_back(i);
            }
        }
        sort(ALL(idx), [&](i32 i, i32 j) -> bool {
            return dist_0[i] < dist_0[j];
        });
        i32 last = y;
        Vec<i32> twos;
        for (i32 i : idx) {
            if (last == y) {
                location[i] = location[0] + dist_0[i];
                stype[i] = 2;
                last = i;
                twos.push_back(location[i]);
                continue;
            }
            i32 d = getDistance(i, last);
            i32 ph = location[last] - d;
            if (ph <= location[y]) {
                location[i] = location[0] + dist_0[i];
                stype[i] = 2;
                last = i;
                twos.push_back(location[i]);
                continue;
            }
            i32 mn = INF;
            for (i32 pos : twos) {
                if (pos > ph) {
                    chmin(mn, pos);
                }
            }
            if (mn - ph + mn - location[0] == dist_0[i]) {
                location[i] = ph;
                stype[i] = 1;
            } else {
                location[i] = location[0] + dist_0[i];
                stype[i] = 2;
                last = i;
                twos.push_back(location[i]);
            }
        }
    }
    
    /*i32 x = 0;
    {
        i32 mn = INF;
        REP(i, 0, n) {
            if (i != y && chmin(mn, dist_y[i])) {
                x = i;
            }
        }
    }
    
    Vec<i32> dist_x(n, 0);
    REP(i, n) {
        if (i != x) {
            dist_x[i] = getDistance(i, x);
        }
    }
    
    location[y] = first + dist_0[y];
    stype[y] = 2;
    location[x] = location[y] - dist_y[x];
    stype[x] = 1;
    
    {
        Vec<i32> idx;
        REP(i, n) {
            if (i != x && i != y && dist_x[i] > dist_y[i]) {
                idx.push_back(i);
            }
        }
        sort(ALL(idx), [&](i32 i, i32 j) -> bool {
            return dist_y[i] < dist_y[j];
        });
        i32 last = x;
        Vec<i32> ones;
        for (i32 i : idx) {
            if (last == x) {
                location[i] = location[y] - dist_y[i];
                stype[i] = 1;
                last = i;
                ones.push_back(location[i]);
                continue;
            }
            i32 d = getDistance(i, last);
            i32 ph = location[last] + d;
            if (ph >= location[x]) {
                location[i] = location[y] - dist_y[i];
                stype[i] = 1;
                last = i;
                ones.push_back(location[i]);
                continue;
            }
            i32 mx = -INF;
            for (i32 pos : ones) {
                if (pos < ph) {
                    chmax(mx, pos);
                }
            }
            if (ph - mx + location[y] - mx == dist_y[i]) {
                location[i] = ph;
                stype[i] = 2;
            } else {
                location[i] = location[y] - dist_y[i];
                stype[i] = 1;
                last = i;
                ones.push_back(location[i]);
            }
        }
    }
    {
        Vec<i32> idx;
        REP(i, n) {
            if (i != x && i != y && dist_x[i] < dist_y[i]) {
                idx.push_back(i);
            }
        }
        sort(ALL(idx), [&](i32 i, i32 j) -> bool {
            return dist_x[i] < dist_x[j];
        });
        i32 last = y;
        Vec<i32> twos;
        for (i32 i : idx) {
            if (last == y) {
                location[i] = location[x] + dist_x[i];
                stype[i] = 2;
                last = i;
                twos.push_back(location[i]);
                continue;
            }
            i32 d = getDistance(i, last);
            i32 ph = location[last] - d;
            if (ph <= location[y]) {
                location[i] = location[x] + dist_x[i];
                stype[i] = 2;
                last = i;
                twos.push_back(location[i]);
                continue;
            }
            i32 mn = INF;
            for (i32 pos : twos) {
                if (pos > ph) {
                    chmin(mn, pos);
                }
            }
            if (mn - ph + mn - location[x] == dist_x[i]) {
                location[i] = ph;
                stype[i] = 1;
            } else {
                location[i] = location[x] + dist_x[i];
                stype[i] = 2;
                last = i;
                twos.push_back(location[i]);
            }
        }
    }*/
}

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