Submission #1312374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312374		anteknne	Rail (IOI14_rail)	C++20	100 / 100	47 ms	600 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 5000 + 17;
pii odl[MAXN];
vector<int> vc;
vector<int> vd;

void findLocation(int N, int first, int location[], int stype[]) {
    for (int i = 1; i < N; i ++) {
        odl[i].nd = i;
        odl[i].st = getDistance(0, i);
    }
    odl[0] = {0, 0};
    sort(odl, odl + N);
    stype[0] = 1;
    location[0] = first;
    vc.pb(first);

    if (N == 1) {
        return;
    }

    stype[odl[1].nd] = 2;
    location[odl[1].nd] = first + odl[1].st;
    vd.pb(location[odl[1].nd]);

    int L = 0, R = odl[1].nd;
    for (int i = 2; i < N; i ++) {
        int a = odl[i].nd;
        int b = getDistance(L, a);
        int c = getDistance(R, a);

        location[a] = -1;

        //do L
        int kand = location[L] + b;
        int pos = -1;
        for (auto x : vc) {
            if (x <= min(kand, location[R])) {
                pos = max(pos, x);
            }
        }

        if (pos != -1 && c == (kand + location[R] - 2 * pos)) {
            location[a] = kand;
            stype[a] = 2;
        }


        //do R
        if (location[a] == -1) {
            int kand = location[R] - c;
            int pos = INT_MAX;
            //cerr << a << ": " << kand << "\n";
            for (auto x : vd) {
                //cerr << x << " ";
                if (x >= max(kand, location[L])) {
                    pos = min(pos, x);
                }
            }
            //cout << "\n";
            //cerr << pos << "\n";

            if (pos != INT_MAX && b == (2 * pos - kand - location[L])) {
                location[a] = kand;
                stype[a] = 1;
            }
        }

        if (location[a] == -1) {
            int kand = location[R] - c;
            int pos = INT_MAX;
            for (auto x : vd) {
                if (x >= location[0]) {
                    pos = min(pos, x);
                }
            }

            if (pos != INT_MAX && odl[i].st == 2 * pos - kand - location[0]) {
                location[a] = kand;
                stype[a] = 1;
            } else {
                location[a] = location[L] + b;
                stype[a] = 2;
            }
        }

        if (stype[a] == 1) {
            if (location[a] < location[L]) {
                L = a;
            }
            vc.pb(location[a]);
        }
        if (stype[a] == 2) {
            if (location[a] > location[R]) {
                R = a;
            }
            vd.pb(location[a]);
        }
    }

    for (int i = 0; i < N; i ++) {
        //cout << odl[i].nd << ": " << stype[odl[i].nd] << "\n";
    }

}

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