Submission #103748

#	Time	Username	Problem	Language	Result	Execution time	Memory
103748		alexpetrescu	Rail (IOI14_rail)	C++14	30 / 100	76 ms	760 KiB

rail

#include "rail.h"
#include <algorithm>
#include <set>
#include <cstdio>

#define INF 1000000000

#define MAXN 5009

int dist[MAXN], perm[MAXN];
std::set < int > C, D;
std::set < int > ::iterator it, it2;

bool cmp(const int &a, const int &b) {
    return dist[a] < dist[b];
}

inline bool notFound(int x) {
    it = C.lower_bound(x);
    if (it != C.end() && *it == x)
        return 0;
    it = D.lower_bound(x);
    if (it != D.end() && *it == x)
        return 0;
    return 1;
}

inline int myGetDistance(int x, char a, int y, char b) {
    if (a == 'C') {
        if (b == 'D') {
            if (x < y)
                return y - x;
            it = D.lower_bound(x);
            if (it == D.end())
                return INF;
            it2 = C.lower_bound(y);
            if (it2 == C.begin())
                return INF;
            it2--;
            return *it - x + *it - *it2 + y - *it2;
        } else {
            it = D.lower_bound(std::max(x, y));
            if (it == D.end())
                return INF;
            return *it - x + *it - y;
        }
    } else if (b == 'C') {
        if (x > y)
            return x - y;
        it = C.lower_bound(x);
        if (it == C.begin())
            return INF;
        it--;
        it2 = D.lower_bound(y);
        if (it2 == D.end())
            return INF;
        return x - *it + *it2 - *it + *it2 - y;
    } else {
        it = C.lower_bound(std::min(x, y));
        if (it == C.begin())
            return INF;
        it--;
        return x - *it + y - *it;
    }
}

inline void solve(int x, int first, int &val, int &tip, int &left, int &right) {
    it = D.end();
    it--;
    int A = *it, B = *(C.begin());
    int dA = getDistance(x, right), dB = getDistance(x, left);

    int d = B + dB, c = A - dA;
    bool okD = (notFound(d) && myGetDistance(A, 'D', d, 'D') == dA && myGetDistance(first, 'C', d, 'D') == dist[x]);
    bool okC = (notFound(c) && myGetDistance(B, 'C', c, 'C') == dB && myGetDistance(first, 'C', c, 'C') == dist[x]);

    if (okD == 0 && okC == 0)
        okD = 1;

    if (okD) {
        val = d;
        tip = 2;
        D.insert(val);
        it = D.upper_bound(val);
        if (it == D.end())
            right = x;
    } else {
        val = c;
        tip = 1;
        C.insert(val);
        it = C.lower_bound(val);
        if (it == C.begin())
            left = x;
    }
}

void findLocation(int N, int first, int location[], int stype[]) {
    location[0] = first;
    stype[0] = 1;
    for (int i = 1; i < N; i++) {
        dist[i] = getDistance(0, i);
        perm[i] = i;
    }
    std::sort(perm + 1, perm + N, cmp);
    location[perm[1]] = first + dist[perm[1]];
    stype[perm[1]] = 2;
    C.insert(first);
    D.insert(location[perm[1]]);
    int left = 0, right = perm[1];
    for (int i = 2; i < N; i++)
        solve(perm[i], first, location[perm[i]], stype[perm[i]], left, right);
}

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