Submission #301648

#	Time	Username	Problem	Language	Result	Execution time	Memory
301648		kevinsogo	Rail (IOI14_rail)	C++17	100 / 100	424 ms	768 KiB

rail

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

#define C 1
#define D 2
#define EMPTY -1

void findLocation(int n, int loc, int locs[], int typs[]) {
    for (int i = 0; i < n; i++) typs[i] = EMPTY;
    locs[0] = loc;
    typs[0] = C;

    if (n >= 2) {
        vector<int> d0(n);
        int xr = -1;
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                d0[i] = getDistance(0, i);
                if (xr == -1 || d0[xr] > d0[i]) xr = i;
            }
        }
        locs[xr] = locs[0] + d0[xr];
        typs[xr] = D;

        vector<int> dxr(n);
        int xl = -1;
        for (int i = 0; i < n; i++) {
            if (i != xr) {
                dxr[i] = getDistance(xr, i);
                if (xl == -1 || dxr[xl] > dxr[i]) xl = i;
            }
        }

        locs[xl] = locs[xr] - dxr[xl];
        typs[xl] = C;

        vector<int> dxl(n), rseq, lseq;
        for (int i = 0; i < n; i++) {
            if (i != xl) {
                dxl[i] = i == 0 ? d0[xl] : d0[i] - (dxr[0] - dxr[xl]);
            }
            if (typs[i] == EMPTY) {
                (dxl[i] < dxr[i] ? rseq : lseq).push_back(i);
            }
        }

        for (int it = 0; it < 2; it++) {
            swap(lseq, rseq);
            swap(xl, xr);
            swap(dxl, dxr);
            for (int i = 0; i < n; i++) {
                if (typs[i] != EMPTY) {
                    typs[i] = typs[i] == C ? D : C;
                    locs[i] = -locs[i];
                }
            }

            vector<int>& seq = rseq;
            sort(seq.begin(), seq.end(), [&dxl](int i, int j) { return dxl[i] < dxl[j]; });
            for (int i : seq) {

                int rightmost_c = xl, rightmost_d = xr;
                for (int i : seq) {
                    if (typs[i] == C) {
                        if (locs[rightmost_c] < locs[i]) rightmost_c = i;
                    }
                    if (typs[i] == D) {
                        if (locs[rightmost_d] < locs[i]) rightmost_d = i;
                    }
                }

                assert(locs[rightmost_c] < locs[rightmost_d]);

                int dr = getDistance(i, rightmost_d);

                auto good = [&](int pos) {
                    for (int i = 0; i < n; i++) {
                        if (typs[i] != EMPTY && locs[i] == pos) return false;
                    }

                    if (pos > locs[rightmost_d]) {
                        if (dxl[i] != pos - locs[xl])
                            return false;

                        int possible_c = pos + locs[rightmost_d] - dr;
                        assert(possible_c % 2 == 0);
                        possible_c >>= 1;
                        if (!(locs[rightmost_c] <= possible_c && possible_c < locs[rightmost_d]))
                            return false;
                        for (int j = 0; j < n; j++) {
                            if (typs[j] == D && locs[j] == possible_c) return false;
                        }
                    } else {
                        assert(pos < locs[rightmost_d]);
                        int rd = rightmost_d;
                        for (int j = 0; j < n; j++) {
                            if (typs[j] == D && pos < locs[j] && locs[j] < locs[rd]) rd = j;
                        }
                        if (dxl[i] != locs[rd] - pos + locs[rd] - locs[xl])
                            return false;
                        if (dr != locs[rightmost_d] - pos)
                            return false;
                    }

                    return true;
                };

                for (int pos : {locs[xl] + dxl[i], locs[rightmost_d] - dr}) {
                    if (good(pos)) {
                        assert(typs[i] == EMPTY);
                        typs[i] = (locs[i] = pos) < locs[rightmost_d] ? C : D;
                    }
                }
                assert(typs[i] != EMPTY);
            }
        }
    }
}

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