Submission #1022912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022912		hmm789	Rail (IOI14_rail)	C++14	100 / 100	53 ms	904 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
 
void findLocation(int N, int first, int location[], int stype[]) {
    int d0[N];
    vector<int> idx;
    for(int i = 1; i < N; i++) {
        d0[i] = getDistance(0, i);
        idx.push_back(i);
    }
    sort(idx.begin(), idx.end(), [&](int a, int b) {return d0[a] < d0[b];});
    int cl = 0, cr = *idx.begin();
    location[cl] = first;
    stype[cl] = 1;
    location[cr] = first+d0[cr];
    stype[cr] = 2;
    idx.erase(idx.begin());
    set<int> s1, s2;
    s1.insert(location[cl]); s2.insert(location[cr]);
    for(int i : idx) {
        int dl = getDistance(i, cl);
        int dr = getDistance(i, cr);
        int pos = (dl-dr+location[cl]+location[cr])/2;
        if(s2.count(pos) || (!s1.count(pos) && pos <= first)) {
            location[i] = location[cr] - dr;
            stype[i] = 1;
            s1.insert(location[i]);
            if(location[i] < location[cl]) cl = i;
        } else {
            location[i] = location[cl] + dl;
            stype[i] = 2;
            s2.insert(location[i]);
            if(location[i] > location[cr]) cr = i;
        }
    }
}

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