Submission #856671

#	Time	Username	Problem	Language	Result	Execution time	Memory
856671		abcvuitunggio	Rail (IOI14_rail)	C++17	100 / 100	51 ms	1100 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;
    set <int> sl,sr;
    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());
    sl.insert(-first);
    sr.insert(first+mn);
    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 (a<0||bs[a])
            ch=1;
        if (a>first&&a<first+mn)
            ch=1;
        else if (a<first)
            ch|=(location[r]+a+*sl.lower_bound(-a)*2!=y);
        else if (b>=0&&!bs[b]){
            if (b>first)
                ch=(*sr.lower_bound(b)*2-location[l]-b==x);
            else
                ch=(y-dist==location[r]-first-mn*2);
        }
        if (ch){
            location[i]=b;
            bs[b]=1;
            stype[i]=1;
            if (location[i]<location[l]){
                l=i;
                sl.insert(-b);
            }
            continue;
        }
        location[i]=a;
        bs[a]=1;
        stype[i]=2;
        if (location[i]>location[r]){
            r=i;
            sr.insert(a);
        }
    }
}

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