Submission #81092

#	Time	Username	Problem	Language	Result	Execution time	Memory
81092		giorgikob	Rail (IOI14_rail)	C++14	100 / 100	197 ms	2264 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>

#define F first
#define Se second
using namespace std;
vector<pair<int,int> >V;
int D[100000],D1[100000];
void findLocation(int n, int first, int location[], int stype[])
{
	for(int i=0;i<n;i++)location[i]=-1;
	location[0]=first;stype[0]=1;
	for(int i=1;i<n;i++)
	{
		int X=getDistance(0,i);
		D[i]=X;
		V.push_back(make_pair(X,i));
	}
	sort(V.begin(),V.end());
	int x=V[0].F,A=0,B=V[0].Se,Ax=first,Bx=first+x;
	location[B]=Bx;stype[B]=2;
	
	D1[0]=D[B];
	for(int i=1;i<n;i++)
	if(i!=B)
	D1[i]=getDistance(B,i);
	
	int distAB=D[B],left=0,right=B;
	for(int i=1;i<V.size();i++)
	{
		int distA=V[i].F,ind=V[i].Se;
		int distB=D1[ind];
//		cout<<ind<<" "<<distA<<" "<<distB<<"<--------"<<endl;
		if(distB<distAB && distA==distB+distAB)
		{
			location[ind]=location[B]-distB;
			stype[ind]=1;
		}
		else
		if(distAB+distB==distA)
		{
			//cout<<ind<<endl;
			int dist_left=getDistance(left,ind);
			int distB_left=D1[left];
			int loc=location[left]+dist_left;
			if(loc>=location[B])
			{
				location[ind]=location[B]-distB;
				stype[ind]=1;
				left=ind;
			}
			else
			{
				//cout<<ind<<" "<<loc<<endl;
				int in=-1,mxlc=-1;
				for(int j=0;j<n;j++)
				if(location[j]>=0)
				if(location[j]<loc && mxlc<location[j])
				in=j,mxlc=location[j];//cout<<in<<endl;
				if(in==-1)
				{
					location[ind]=location[B]-distB;
					stype[ind]=1;
					left=ind;
				}
				else
				if(D1[in]+(dist_left-(location[in]-location[left]))==distB)
				{
					location[ind]=loc;
					stype[ind]=2;
				}
				else
				{
					location[ind]=location[B]-distB;
					stype[ind]=1;
					left=ind;
				}
			}
		}
		else
		{
			int dist_right=getDistance(right,ind);
			int distA_right=D[right];
			int loc=location[right]-dist_right;
			if(loc<=location[B])
			{
				location[ind]=location[A]+distA;
				stype[ind]=2;
				right=ind;
			}
			else
			{
				int in=-1,mxlc=1e9;
				for(int j=0;j<n;j++)
				if(location[j]>=0)
				if(location[j]>loc && location[j]<mxlc)
				in=j,mxlc=location[j];
				if(in==-1)
				{
					location[ind]=location[A]+distA;
					stype[ind]=2;
					right=ind;
				}
				else
				if(D[in]+(dist_right-(location[right]-location[in]))==distA)
				{
					location[ind]=loc;
					stype[ind]=1;
				}
				else
				{
					location[ind]=location[A]+distA;
					stype[ind]=2;
					right=ind;
				}
			}
		}
		
	}
	//for(int i=0;i<n;i++)
	//cout<<i<<" "<<location[i]<<" "<<stype[i]<<endl;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<V.size();i++)
              ~^~~~~~~~~
rail.cpp:44:8: warning: unused variable 'distB_left' [-Wunused-variable]
    int distB_left=D1[left];
        ^~~~~~~~~~
rail.cpp:83:8: warning: unused variable 'distA_right' [-Wunused-variable]
    int distA_right=D[right];
        ^~~~~~~~~~~
rail.cpp:20:29: warning: unused variable 'Ax' [-Wunused-variable]
  int x=V[0].F,A=0,B=V[0].Se,Ax=first,Bx=first+x;
                             ^~

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