Submission #1218281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218281		HappyCapybara	Rail (IOI14_rail)	C++20	100 / 100	46 ms	1104 KiB

rail

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

vector<int> d0, dx;

void findLocation(int N, int first, int location[], int stype[]){
    location[0] = first;
    stype[0] = 1;
    if (N == 1) return;
    set<pair<int,int>> cs, ds;
    set<int> cls, dls;
    cs.insert({first, 0});
    cls.insert(first);
    d0.resize(N);
    d0[0] = 0;
    for (int i=1; i<N; i++) d0[i] = getDistance(0, i);
    pair<int,int> cl = {pow(10, 7), -1};
    for (int i=1; i<N; i++) cl = min(cl, {d0[i], i});
    int x = cl.second;
    dx.resize(N);
    dx[x] = 0;
    dx[0] = d0[x];
    location[x] = first+d0[x];
    stype[x] = 2;
    ds.insert({-location[x], x});
    dls.insert(location[x]);
    vector<int> l, m, r;
    for (int i=1; i<N; i++){
        if (i == x) continue;
        dx[i] = getDistance(x, i);
        if (d0[i] == d0[x]+dx[i] && dx[i] < d0[x]) m.push_back(i);
        else if (d0[i] == d0[x]+dx[i]) l.push_back(i);
        else r.push_back(i);
    }
    for (int i : m){
        location[i] = location[x]-dx[i];
        stype[i] = 1;
        cs.insert({location[i], i});
        cls.insert(location[i]);
    }
    sort(l.begin(), l.end(), [](int a, int b){return d0[a] < d0[b];});
    for (int i : l){
        auto [yl, y] = *cs.begin();
        int dy = getDistance(y, i);
        int z = dx[i]-dx[y]-dy;
        z = -z;
        int pl = yl+z/2+dx[i]-(location[x]-(yl+z/2));
        if (pl < location[0] && cls.find(yl+z/2) != cls.end()){
            location[i] = pl;
            stype[i] = 2;
            ds.insert({-location[i], i});
            dls.insert(location[i]);
        }
        else {
            location[i] = location[x]-dx[i];
            stype[i] = 1;
            cs.insert({location[i], i});
            cls.insert(location[i]);
        }
    }
    sort(r.begin(), r.end(), [](int a, int b){return d0[a] < d0[b];});
    for (int i : r){
        auto [yl, y] = *ds.begin();
        yl = -yl;
        int dy = getDistance(y, i);
        int z = d0[i]-d0[y]-dy;
        z = -z;
        int pl = yl-z/2-(d0[i]-((yl-z/2)-location[0]));
        if (pl > location[x] && dls.find(yl-z/2) != dls.end()){
            location[i] = pl;
            stype[i] = 1;
            cs.insert({location[i], i});
            cls.insert(location[i]);
        }
        else {
            location[i] = location[0]+d0[i];
            stype[i] = 2;
            ds.insert({-location[i], i});
            dls.insert(location[i]);
        }
    }
    /*cout << endl;
    for (int i=0; i<N; i++){
        cout << stype[i] << " " << location[i] << endl;
    }*/
}

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