Submission #1310997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310997		M_W_13	Rail (IOI14_rail)	C++20	100 / 100	52 ms	592 KiB

rail

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int INF = 1e9;

void findLocation(int n, int first, int location[], int stype[])
{
    vector<pii> vec;
    location[0] = first;
    stype[0] = 1;
    if (n == 1) return ;
    int dl[n];
    for (int i = 1; i < n; i++) {
        int x = getDistance(0, i);
        vec.pb({x, i});
        dl[i] = x;
    }
    sort(all(vec));
    int x = 0;
    int y = vec[0].nd;
    location[y] = location[x] + vec[0].st;
    stype[y] = 2;
    vector<int> znane;
    znane.pb(0);
    znane.pb(y);
    int sz = vec.size();
    for (int it = 1; it < sz; it++) {
        pii p = vec[it];
        int i = p.nd;
        int a = getDistance(x, i);
        int b = getDistance(y, i);
        int px = location[x];
        int py = location[y];
        // cout << "i = " << i << " location = " << location[i] << " stype = " << stype[i] << " x = " << x << " y = " << y << " px = " << px << " py = " << py << '\n';
        int dla = INF;
        int dlb = INF;
        // cout << "possiblea = " << px + a << " " << "possible b = " << py - b << '\n';
        for (auto v: znane) {
            // cout << "v = " << v << " stype = " << stype[v] << " loc = " << location[v] << '\n';
            if (stype[v] == 1) {
                if (location[v] >= (px + a)) continue;
                dlb = min(dlb, py - location[v] + px + a - location[v]);
            }
            else {
                if (location[v] <= (py - b)) continue;
                dla = min(dla, location[v] - px + location[v] - (py - b));
            }
        }
        // cout << "a = " << a << " b = " << b << '\n';
        // cout << "dla = " << dla << " dlb = " << dlb << '\n';
        znane.pb(i);
        if (dlb == b) {
            location[i] = px + a;
            stype[i] = 2;
            if ((px + a) > py) {
                y = i;
            }
        }
        else if (dla == a) {
            location[i] = py - b;
            stype[i] = 1;
            if ((py - b) < px) {
                x = i;
            }
        }
        else {
            location[i] = location[0] + dl[i];
            if (location[i] == (px + a)) {
                stype[i] = 2;
                if (location[i] > location[y]) y = i;
            }
            else {
                location[i] = py - b;
                stype[i] = 1;
                if (location[i] < location[x]) x = i;
            }
        }
        // cout << "FOUND = " << location[i] << '\n';
    }
}

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