Submission #426261

#	Time	Username	Problem	Language	Result	Execution time	Memory
426261		someone	Rail (IOI14_rail)	C++14	100 / 100	100 ms	760 KiB

rail

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

struct Val {
    int i, val;
};

const int N = 1e4;

int n;
vector<Val> dist;
unordered_map<int, int> id;

void findLocation(int n1, int first, int location[], int stype[]) {
    n = n1;
    stype[0] = 1;
    location[0] = first;
    if(n == 1)
        return;

    for(int i = 1; i < n; i++)
        dist.push_back({i, getDistance(0, i)});
    sort(dist.begin(), dist.end(),
    [](Val a, Val b) {
        return a.val < b.val;
    });

    id[location[0]] = 0;
    stype[dist[0].i] = 2;
    location[dist[0].i] = first + dist[0].val;
    id[location[dist[0].i]] = dist[0].i;

    int l = 0, r = dist[0].i;
    for(int i = 1; i < n-1; i++) {
        int a = getDistance(l, dist[i].i),
            b = getDistance(r, dist[i].i),
            p = (a - b + location[l] + location[r])/2;
        if(id.find(p) == id.end()) {
            if(p > first) {
                stype[dist[i].i] = 2;
                location[dist[i].i] = location[l] + a;
            } else {
                stype[dist[i].i] = 1;
                location[dist[i].i] = location[r] - b;
            }
        } else {
            int j = id[p];
            if(stype[j] == 1) {
                stype[dist[i].i] = 2;
                location[dist[i].i] = location[l] + a;
            } else {
                stype[dist[i].i] = 1;
                location[dist[i].i] = location[r] - b;
            }
        }
        if(stype[dist[i].i] == 1 && location[dist[i].i] < location[l])
            l = dist[i].i;
        if(stype[dist[i].i] == 2 && location[dist[i].i] > location[r])
            r = dist[i].i;
        id[location[dist[i].i]] = dist[i].i;
    }
}

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