Submission #1032294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032294		vjudge1	Rail (IOI14_rail)	C++17	30 / 100	46 ms	15972 KiB

rail

#include "rail.h"

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

int lst[1000100];
int dist[1000100];
int pp[1000100];

void findLocation(int N, int first, int location[], int stype[])
{
    memset(lst,-1,sizeof(lst));
    location[0]=first;
    stype[0]=1;
    lst[first]=0;
    int n=N;
    if(n==1)return;
    #define loc location
    #define ty stype
    for(int i=1;i<n;i++){
        dist[i]=getDistance(0,i);
    }
    for(int i=0;i<n;i++){
        pp[i]=i;
    }
    sort(pp+1,pp+n,[&](int i,int j)->bool {
        return dist[i]<dist[j];
    });
    int cl=pp[1];
    lst[location[cl]=first+dist[cl]]=cl;
    stype[cl]=2;
    int l=0,r=cl;
    for(int i=2;i<n;i++){
        int p=pp[i];
        int k=getDistance(cl,p);
        if(dist[p]==dist[cl]+k){
            if(k<dist[cl]){
                ty[p]=1;
                lst[loc[p]=loc[cl]-k]=p;
            }else if(l==0){
                l=p;
                ty[p]=1;
                lst[loc[p]=loc[cl]-k]=p;
            }else{
                int dd=getDistance(l,p);
                int possible=loc[l]+dd;
                int x=(k-(loc[cl]-possible))/2;
                if(loc[0]<=possible||possible-x<loc[l]||lst[possible]!=-1){
                    ty[p]=1;
                    lst[loc[p]=loc[cl]-k]=p;
                    l=p;
                    continue;
                }
                int guy=lst[possible-x];
                assert(0<=guy&&guy<n);
                if(ty[guy]==1){
                    ty[p]=2;
                    lst[loc[p]=possible]=p;
                }else{
                    ty[p]=1;
                    lst[loc[p]=loc[cl]-k]=p;
                    l=p;
                }
            }
        }else{
            k=dist[p];
            if(r==cl){
                r=p;
                ty[p]=2;
                lst[loc[p]=loc[0]+k]=p;
            }else{
                int dd=getDistance(r,p);
                int possible=loc[r]-dd;
                int x=(k-(possible-loc[0]))/2;
                if(possible<=loc[cl]||loc[r]<possible+x||lst[possible]!=-1){
                    ty[p]=2;
                    lst[loc[p]=loc[0]+k]=p;
                    r=p;
                    continue;
                }
                int guy=lst[possible+x];
                assert(0<=guy&&guy<n);
                if(ty[guy]==2){
                    ty[p]=1;
                    lst[loc[p]=possible]=p;
                }else{
                    ty[p]=2;
                    lst[loc[p]=loc[0]+k]=p;
                    r=p;
                }
            }
        }
    }
}

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