Submission #993803

#	Time	Username	Problem	Language	Result	Execution time	Memory
993803		12345678	Rail (IOI14_rail)	C++17	100 / 100	51 ms	916 KiB

rail

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

using namespace std;

const int nx=5e3+5;

int l, r, vl[nx];
vector<pair<int, int>> d;
set<int> C, D;

void findLocation(int N, int first, int location[], int stype[])
{
    location[0]=first;
    stype[0]=1;
    for (int i=1; i<N; i++) vl[i]=getDistance(0, i);
    for (int i=1; i<N; i++) d.push_back({vl[i], i});
    sort(d.begin(), d.end());
    //cout<<"p "<<d[0].second<<'\n';
    location[d[0].second]=first+d[0].first;
    stype[d[0].second]=2;
    l=0, r=d[0].second;
    C.insert(first);
    D.insert(first+d[0].first);
    for (int i=1; i<N-1; i++)
    {
        int u=d[i].second, dl=getDistance(l, u), dr=getDistance(r, u), pos=location[l]+dl;
        if (location[r]-*(prev(C.upper_bound(pos)))+pos-*(prev(C.upper_bound(pos)))==dr) location[u]=pos, D.insert(pos), stype[u]=2;
        else
        {
            pos=location[r]-dr;
            if (*D.lower_bound(pos)-location[l]+*D.lower_bound(pos)-pos==dl) location[u]=pos, C.insert(pos), stype[u]=1;
            else if (d[i].first==2*location[d[0].second]-first-pos) location[u]=pos, C.insert(pos), stype[u]=1;
            else location[u]=location[l]+dl, D.insert(location[u]), stype[u]=2;
        }
        if (location[u]<location[l]) l=u;
        if (location[u]>location[r]) r=u;
    }
}

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