Submission #349609

#	Time	Username	Problem	Language	Result	Execution time	Memory
349609		juggernaut	Rail (IOI14_rail)	C++14	100 / 100	97 ms	780 KiB

rail

/*
Kak mydryi chelovek govoril glavnoya ponyat a ne napisat
*/
#include "rail.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
int d0[5001], d1[5001];
void findLocation(int N, int first, int l[], int s[]){
	for(int i = 0 ; i < N; i++){
		l[i]=-1;
		s[i]=-1;
	}
	int len = 2e9, ind ;
	vector <pair <int, int> > left, right;
	for (int  i = 1; i < N; i++){
		d0[i] = getDistance(0, i);
		if(d0[i] < len ){
			len = d0[i];
			ind = i;
		}
	}
	l[0]=first;
	s[0] = 1;
	l[ind] = first + len;
	s[ind] = 2;
	for (int  i = 0; i < N; i++){
		if( ind !=i){
			d1[i] = getDistance( ind, i);
		}
	}
	for (int  i = 1; i < N; i++){
		if(i != ind){
			if( d0[i] ==  len + d1[i]){
				if(len > d1[i]){
					l[i] = l[ind] - d1[i];
					s[i]=1;	
				}
				else{
					left.push_back( make_pair (d1[i], i));
				}
			}
			else
					right.push_back( make_pair (d0[i], i));
		}
	}
	sort(left.begin() , left.end());
	sort(right.begin() , right.end());
	int R = ind; 
	for(int i = 0 ; i < right.size();i++){
		int ds = getDistance( R , right[i].second);
		int gap = ( d0[R] + ds - d0[right[i].second] )/  2;
		bool flag = true;
		for(int j = 0; j < N; j++){
			if( l[R] - gap == l[j] && s[j] == 2){
				flag = 0;
				l[right[i].second] = l[R] - ds;
				s[right[i].second] = 1;
				break;
			}
			
		}
		if(flag){
			l[right[i].second] = first + d0[right[i].second];
			s[right[i].second] = 2;	
			R = right[i].second;
		}
	}
	R = 0; 
	for(int i = 0 ; i < left.size();i++){
		int ds = getDistance( R , left[i].second);
		int gap = ( d1[R] + ds - d1[left[i].second] )/  2;
		bool flag = true;
		for(int j = 0; j < N; j++){
			if( l[R] + gap == l[j] && s[j] == 1){
				flag = 0;
				l[left[i].second] = l[R] + ds;
				s[left[i].second] = 2;
				break;
			}
		}
		if(flag){
			l[left[i].second] = l[ind] - d1[left[i].second];
			s[left[i].second] = 1;	
			R = left[i].second;
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0 ; i < right.size();i++){
      |                  ~~^~~~~~~~~~~~~~
rail.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0 ; i < left.size();i++){
      |                  ~~^~~~~~~~~~~~~
rail.cpp:25:4: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |  l[ind] = first + len;
      |    ^~~

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