Submission #349242

#	Time	Username	Problem	Language	Result	Execution time	Memory
349242		tengiz05	Rail (IOI14_rail)	C++17	100 / 100	89 ms	4588 KiB

rail

#include "rail.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pii pair<int,int>
#define ff first
#define ss second
const int MAXN = 5005, MM = 1e6+5;
int d0[MAXN], d1[MAXN], n;
int Type[MM];
void findLocation(int N, int first, int location[], int stype[]){
	n = N;
	for(int i=1;i<n;i++)d0[i] = getDistance(0,i);
	stype[0]=1;
	location[0]=first;
	Type[first] = 1;
	if(n == 1)return;
	int cherez, mn = 1e9;
	for(int i=1;i<n;i++){
		if(mn > d0[i]){
			mn = d0[i];
			cherez = i;
		}
	}
	stype[cherez]=2;
	location[cherez] = d0[cherez]+first;
	Type[location[cherez]] = 2;
	vector<pii> left, right;
	for(int i=0;i<n;i++){
		if(i != cherez){
			d1[i] = getDistance(cherez, i);
		}
	}
	for(int i=1;i<n;i++){
		if(i != cherez){
			if(d0[i] == d0[cherez] + d1[i]){
				if(d0[cherez] > d1[i]){
					stype[i] = 1;
					location[i] = location[cherez] - d1[i];
					Type[location[i]] = 1;
				}else left.push_back({d1[i],i});
			}
			else right.push_back({d0[i],i});
		}
	}
	sort(all(left));
	sort(all(right));
	int L = 0;
	for(auto [dist, i] : left){
		int t = getDistance(L, i);
		int gap = (d1[L] + t - d1[i])/2;
		if(Type[location[L] + gap] == 1){
			location[i] = location[L]+t;
			stype[i] = 2;
			Type[location[i]] = 2;
		}else {
			location[i] = location[cherez] - d1[i];
			stype[i] = 1;
			Type[location[i]] = 1;
			L = i;
		}
	}
	int R = cherez;
	for(auto [dist, i] : right){
		int t = getDistance(R, i);
		int gap = (d0[R] + t - d0[i])/2;
		if(Type[location[R] - gap] == 2){
			location[i] = location[R]-t;
			stype[i] = 1;
			Type[location[i]] = 1;
		}else {
			location[i] = location[0] + d0[i];
			stype[i] = 2;
			Type[location[i]] = 2;
			R = i;
		}
	}
	return;
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:38:3: warning: 'cherez' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |   if(i != cherez){
      |   ^~

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