Submission #541245

#	Time	Username	Problem	Language	Result	Execution time	Memory
541245		dxz05	Rail (IOI14_rail)	C++14	30 / 100	68 ms	468 KiB

rail

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

using namespace std;

void findLocation(int N, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;

    vector<int> dist(N);
    for (int i = 1; i < N; i++) dist[i] = getDistance(0, i);

    vector<int> perm(N - 1);
    iota(perm.begin(), perm.end(), 1);

    sort(perm.begin(), perm.end(), [&](int i, int j){
        return dist[i] < dist[j];
    });

    set<int> C, D;
    C.insert(first);

    int P = perm[0];
    perm.erase(perm.begin());

    location[P] = first + dist[P];
    stype[P] = 2;
    D.insert(location[P]);

    int L = 0, R = P;
    for (int i : perm){
        int dL = getDistance(i, L), dR = getDistance(i, R);

        int pos = location[L] + dL;
        int p = *--C.upper_bound(pos);
        if (pos < R && dR == pos - p + location[R] - p){
            location[i] = pos;
            stype[i] = 2;
            D.insert(location[i]);
            if (location[i] > location[R]) R = i;
            continue;
        }

        pos = location[L] + dL;
        p = *--C.upper_bound(location[R]);
        if (pos > R && dR == pos - p + location[R] - p){
            location[i] = pos;
            stype[i] = 2;
            D.insert(location[i]);
            if (location[i] > location[R]) R = i;
            continue;
        }

        pos = location[R] - dR;
        p = *D.upper_bound(location[L]);
        if (pos < L && dL == p - pos + p - location[L]){
            location[i] = pos;
            stype[i] = 1;
            C.insert(location[i]);
            if (location[i] < location[L]) L = i;
            continue;
        }

        pos = location[R] - dR;
        p = *D.upper_bound(pos);
        if (pos > L && dL == p - pos + p - location[L]){
            location[i] = pos;
            stype[i] = 1;
            C.insert(location[i]);
            if (location[i] < location[L]) L = i;
            continue;
        }
    }
}

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