Submission #622794

#	Time	Username	Problem	Language	Result	Execution time	Memory
622794		yuto1115	Rail (IOI14_rail)	C++17	100 / 100	233 ms	644 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

void findLocation(int n, int first, int location[], int stype[]) {
    if (n == 1) {
        location[0] = first;
        stype[0] = 1;
        return;
    }
    vi dl(n), dr(n);
    rep2(i, 1, n) dl[i] = getDistance(0, i);
    int r = min_element(dl.begin() + 1, dl.end()) - dl.begin();
    location[r] = first + dl[r];
    stype[r] = 2;
    rep(i, n) if (i != r) dr[i] = getDistance(r, i);
    int l = 0;
    rep(i, n) if (i != r and dr[i] < dr[l]) l = i;
    location[l] = location[r] - dr[l];
    stype[l] = 1;
    if (l) {
        int x = dr[0] * 2 - dl[l];
        swap(dl[0], dl[l]);
        rep2(i, 1, n) if (i != l) dl[i] -= x;
    }
//    cerr << l << ' ' << r << endl;
//    rep(i, n) cerr << dl[i] << ' ' << dr[i] << endl;
    auto f = [&](vi v) {
        sort(all(v), [&](int i, int j) { return dl[i] < dl[j]; });
        set<int> st;
        int now = r;
        for (int i: v) {
            int d = getDistance(now, i);
            if (st.count((dl[now] + dl[i] - d) / 2)) {
                location[i] = dl[now] - d;
                stype[i] = 1;
            } else {
                location[i] = dl[i];
                stype[i] = 2;
                now = i;
                st.insert(dl[i]);
            }
        }
    };
    vi a, b;
    rep(i, n) {
        if (i == l or i == r) continue;
        if (dl[i] < dr[i]) a.pb(i);
        else b.pb(i);
    }
    rep(_, 2) {
        f(a);
        swap(l, r);
        swap(dl, dr);
        swap(a, b);
    }
    for (int i: a) location[i] += location[l];
    for (int i: b) {
        location[i] = location[r] - location[i];
        stype[i] = 3 - stype[i];
    }
}

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