Submission #91877

#	Time	Username	Problem	Language	Result	Execution time	Memory
91877		KLPP	Rail (IOI14_rail)	C++14	100 / 100	94 ms	764 KiB

rail

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

void findLocation(int N, int first, int location[], int stype[])
{

    int n=N;

    for(int i=0;i<n;i++){
        location[i]=-1;
        stype[i]=-1;
    }
    location[0]=first;
    stype[0]=1;

    int dist0[n];
    dist0[0]=0;
    for(int i=1;i<n;i++){
        dist0[i]=getDistance(0,i);
    }
    int m=1;
    for(int i=1;i<n;i++){
        if(dist0[i]<dist0[m])m=i;
    }
    int distm[n];
    for(int i=0;i<n;i++){
        if(i==m)distm[i]=0;
        else{
            distm[i]=getDistance(m,i);
        }
    }
    stype[m]=2;
    location[m]=location[0]+dist0[m];

    vector<pair<int,int> > vleft;
    vector<pair<int,int> >vright;
    for(int i=0;i<n;i++){
        if(i==0){
            vleft.push_back(pair<int,int>(distm[i],i));
        }
        else if(i==m){
            vright.push_back(pair<int,int>(dist0[i],i));
        }
        else if(dist0[i]==distm[i]+dist0[m]){
            vleft.push_back(pair<int,int>(distm[i],i));
        }else{
            vright.push_back(pair<int,int>(dist0[i],i));
        }
    }
    sort(vleft.begin(),vleft.end());
    sort(vright.begin(),vright.end());
    vector<int> C;
    for(int i=0;i<vleft.size();i++){
        //cout<<vleft[i].first<<" "<<vleft[i].second<<endl;
        if(C.size()==0){
            C.push_back(vleft[i].second);
            location[vleft[i].second]=location[m]-vleft[i].first;
            stype[vleft[i].second]=1;
        }else if(stype[vleft[i].second]==-1){
            int d=getDistance(vleft[i].second,C[C.size()-1]);
            int posC=location[m]-vleft[i].first;
            int posD=location[C[C.size()-1]]+d;
            int lo,hi;
            lo=-1;
            hi=C.size();
            while(hi-lo>1){
                int mid=(hi+lo)/2;
                if(location[C[mid]]>posD){
                    lo=mid;
                }else hi=mid;
            }//cout<<C[C.size()-1]<<endl;
            //cout<<hi<<" "<<C[hi]<<" "<<posD<<" "<<d<<endl;
            if(posD+location[m]-2*location[C[hi]]==vleft[i].first){
                location[vleft[i].second]=posD;
                stype[vleft[i].second]=2;
            }else{
                C.push_back(vleft[i].second);
                location[vleft[i].second]=posC;
                stype[vleft[i].second]=1;
            }
        }else{//cout<<"A"<<endl;
            //cout<<stype[vleft[i].second]<<endl;
            if(stype[vleft[i].second]==1){//cout<<vleft[i].second<<endl;
                C.push_back(vleft[i].second);
            }
        }

        /*cout<<"vect:"<<endl;
        for(int j=0;j<C.size();j++)cout<<C[j]<<" ";
        cout<<endl;*/
    }
    vector<int> D;
    for(int i=0;i<vright.size();i++){
        //cout<<vright[i].first<<" A "<<vright[i].second<<endl;
        if(D.size()==0){
            D.push_back(vright[i].second);
            location[vright[i].second]=location[0]+vright[i].first;
            stype[vright[i].second]=2;
        }else if(stype[vright[i].second]==-1){
            int d=getDistance(vright[i].second,D[D.size()-1]);
            int posD=location[0]+vright[i].first;
            int posC=location[D[D.size()-1]]-d;
            int lo,hi;
            lo=-1;
            hi=D.size();
            while(hi-lo>1){
                int mid=(hi+lo)/2;
                if(location[D[mid]]<posC){
                    lo=mid;
                }else hi=mid;
            }//cout<<C[C.size()-1]<<endl;
            //cout<<hi<<" "<<D[hi]<<" "<<posC<<" "<<d<<endl;
            if(posC+location[0]-2*location[D[hi]]==-vright[i].first){
                location[vright[i].second]=posC;
                stype[vright[i].second]=1;
            }else{
                D.push_back(vright[i].second);
                location[vright[i].second]=posD;
                stype[vright[i].second]=2;
            }
        }else{//cout<<"A"<<endl;
            //cout<<stype[vleft[i].second]<<endl;
            if(stype[vright[i].second]==2){//cout<<vleft[i].second<<endl;
                D.push_back(vright[i].second);
            }
        }
        /*for(int j=0;j<D.size();j++)cout<<D[j]<<" ";
        cout<<endl;*/
    }


    /*for(int i=0;i<n;i++){
        cout<<stype[i]<<" "<<location[i]<<endl;
    }*/
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<vleft.size();i++){
                 ~^~~~~~~~~~~~~
rail.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<vright.size();i++){
                 ~^~~~~~~~~~~~~~

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