Submission #1139485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139485		BlockOG	Rail (IOI14_rail)	C++20	100 / 100	614 ms	1548 KiB

rail

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

// mrrrow meeeow nyaa :3c
// play vivid/stasis! it's a really awesome free game on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)

#define pb push_back
#define pob pop_back
#define p push
#define po pop
#define f first
#define s second
#define ub upper_bound
#define lb lower_bound
#define be(a) a.begin(), a.end()

using namespace std;

int ____init = []
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

map<pair<int, int>, int> cache;
int dist(int i, int j)
{
    if (i == j)
        return 0;
    if (i > j)
        swap(i, j);
    if (cache.count({i, j}))
        return cache[{i, j}];
    return cache[{i, j}] = getDistance(i, j);
}

void findLocation(int n, int first, int location[], int stype[])
{
    vector<int> b;

    location[0] = first;
    stype[0] = 1;
    fo(i, 1, n)
    {
        location[i] = first + dist(0, i), stype[i] = 2;
        b.pb(i);
    }

    sort(be(b), [&](int &i, int &j)
         { return location[i] < location[j]; });

    vector<int> c;
    vector<int> d;
    for (int i : b)
    {
        of(j, 0, c.size())
        {
            if (dist(0, i) == dist(0, c.back()) + dist(c.back(), i) - 2 * (location[c.back()] - location[c[j]]))
            {
                location[i] = location[c.back()] - dist(c.back(), i);
                stype[i] = 1;
                if (location[i] < first)
                    d.pb(i);

                goto cont;
            }
        }

        c.pb(i);

    cont:;
    }

    sort(be(d), [&](int &i, int &j)
         { return location[i] > location[j]; });

    vector<int> e;
    for (int i : d)
    {
        of(j, 0, e.size())
        {
            if (dist(0, i) == dist(0, e.back()) + dist(e.back(), i) - 2 * (location[e[j]] - location[e.back()]))
            {
                location[i] = location[e.back()] + dist(e.back(), i);
                stype[i] = 2;

                goto cont2;
            }
        }

        e.pb(i);

    cont2:;
    }
}

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