Submission #889512

#	Time	Username	Problem	Language	Result	Execution time	Memory
889512		JakobZorz	Rail (IOI14_rail)	C++17	100 / 100	67 ms	980 KiB

rail

#include"rail.h"
#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;

void findLocation(int n,int first,int location[],int stype[]){
    int calls=0;
    vector<pair<int,int>>dist0;
    vector<int>dist_from_0(n);
    for(int i=1;i<n;i++){
        dist_from_0[i]=getDistance(0,i);
        calls++;
        dist0.emplace_back(dist_from_0[i],i);
    }
    sort(dist0.begin(),dist0.end());
    
    int left=0,right=0;
    stype[0]=1;
    location[0]=0;
    
    //for(auto i:dist0)
        //cout<<i.first<<" "<<i.second<<"\n";
    
    for(auto[dist,i]:dist0){
        if(right==0){
            right=i;
            location[i]=dist;
            stype[i]=2;
            continue;
        }
        
        int dist1=getDistance(dist0[0].second,i);
        calls++;
        if(dist1+dist0[0].first==dist){ // i is on the left side
            dist-=2*dist0[0].first;
            if(dist<0){
                location[i]=-dist;
                stype[i]=1;
                continue;
            }
            
            if(left==0){
                location[i]=-dist;
                stype[i]=1;
                left=i;
                continue;
            }
            
            int dist2=getDistance(left,i);
            int mid=(location[left]+dist2-dist)/2;
            
            bool is_left=false;
            for(int i=0;i<n;i++){
                if(location[i]==mid&&stype[i]==1){
                    is_left=true;
                }
            }
            
            if(dist2>location[left]&&is_left){
                location[i]=location[left]+dist2;
                stype[i]=2;
            }else{
                left=i;
                location[i]=-dist;
                stype[i]=1;
            }
            
        }else{ // i is on the right side
            int dist2=getDistance(right,i);
            int mid=(location[right]-dist2+dist)/2;
            
            bool is_left=false;
            for(int i=0;i<n;i++){
                if(location[i]==mid&&stype[i]==2){
                    is_left=true;
                }
            }
            
            if(dist2<location[right]&&is_left){
                location[i]=location[right]-dist2;
                stype[i]=1;
            }else{
                right=i;
                location[i]=dist;
                stype[i]=2;
            }
        }
    }
    
    for(int i=0;i<n;i++){
        location[i]+=first;
        //if(n<20) cout<<stype[i]<<" "<<location[i]<<"\n";
    }
    
    //cout<<"limit: "<<3*(n-1)<<" calls: "<<calls<<"\n";
}

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