oj.uz

Submission #349609

# Submission time Handle Problem Language Result Execution time Memory
349609 2021-01-18T02:21:19 Z juggernaut Rail (IOI14_rail) C++14
100 / 100
 97 ms 780 KB 
/*
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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 380 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 620 KB Output is correct
2 Correct 94 ms 620 KB Output is correct
3 Correct 95 ms 780 KB Output is correct
4 Correct 93 ms 620 KB Output is correct
5 Correct 94 ms 620 KB Output is correct
6 Correct 94 ms 620 KB Output is correct
7 Correct 97 ms 748 KB Output is correct
8 Correct 94 ms 620 KB Output is correct
9 Correct 95 ms 620 KB Output is correct
10 Correct 93 ms 620 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 620 KB Output is correct
2 Correct 96 ms 748 KB Output is correct
3 Correct 92 ms 620 KB Output is correct
4 Correct 94 ms 620 KB Output is correct
5 Correct 95 ms 748 KB Output is correct
6 Correct 95 ms 620 KB Output is correct
7 Correct 95 ms 620 KB Output is correct
8 Correct 94 ms 656 KB Output is correct
9 Correct 94 ms 620 KB Output is correct
10 Correct 93 ms 620 KB Output is correct
11 Correct 96 ms 620 KB Output is correct
12 Correct 93 ms 620 KB Output is correct
13 Correct 94 ms 620 KB Output is correct
14 Correct 94 ms 748 KB Output is correct
15 Correct 94 ms 748 KB Output is correct
16 Correct 93 ms 620 KB Output is correct
17 Correct 93 ms 620 KB Output is correct
18 Correct 93 ms 620 KB Output is correct
19 Correct 94 ms 620 KB Output is correct
20 Correct 94 ms 620 KB Output is correct