Submission #856664

#	Time	Username	Problem	Language	Result	Execution time	Memory
856664		abcvuitunggio	Rail (IOI14_rail)	C++17	30 / 100	44 ms	856 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
    bitset <1000001> bs;
    int d[N],mn=1e9,l=0,r=-1;
    location[0]=first;
    stype[0]=1;
    vector <pair <int, int>> ve;
    vector <int> vl;
    for (int i=1;i<N;i++){
        d[i]=getDistance(0,i);
        if (d[i]<mn){
            mn=d[i];
            r=i;
        }
    }
    location[r]=first+mn;
    bs[first]=1;
    bs[first+mn]=1;
    stype[r]=2;
    for (int i=1;i<N;i++)
        if (i!=r)
            ve.emplace_back(d[i],i);
    sort(ve.begin(),ve.end());
    vl.push_back(-first);
    for (auto [dist,i]:ve){
        int x=getDistance(l,i),y=getDistance(r,i);
        int a=location[l]+x,b=location[r]-y;
        bool ch=0;
        if (bs[a])
            ch=1;
        if (a>first&&a<first+mn)
            ch=1;
        else
            ch|=(location[r]+a+vl[lower_bound(vl.begin(),vl.end(),-a)-vl.begin()]*2!=y);
        if (ch){
            location[i]=b;
            bs[b]=1;
            stype[i]=1;
            if (location[i]<location[l]){
                l=i;
                vl.push_back(-b);
            }
            continue;
        }
        location[i]=a;
        bs[a]=1;
        stype[i]=2;
        if (location[i]>location[r])
            r=i;
    }
}

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