Submission #588254

#	Time	Username	Problem	Language	Result	Execution time	Memory
588254		AlperenT	Rail (IOI14_rail)	C++17	100 / 100	119 ms	656 KiB

rail

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

using namespace std;

void findLocation(int n, int A, int location[], int stype[]){
	location[0] = A;
	stype[0] = 1;

	A = 0;
	
	if(n == 1) return;

	int distA[n] = {};
	int distB[n] = {};

	for(int i = 1; i < n; i++){
		distA[i] = getDistance(A, i);
	}

	int B = min_element(distA + 1, distA + n) - distA;

	location[B] = location[A] + distA[B];
	stype[B] = 2;

	vector<pair<int, int>> lft, rght;

	for(int i = 1; i < n; i++){
		if(i != B){
			distB[i] = getDistance(B, i);

			if(distA[i] == distA[B] + distB[i]) lft.push_back({distB[i], i});
			else rght.push_back({distA[i], i});
		}
	}

	sort(lft.begin(), lft.end());

	if(!lft.empty()){
		int C = lft.front().second;

		location[C] = location[B] - distB[C];
		stype[C] = 1;

		for(int i = 1; i < lft.size(); i++){
			int X = lft[i].second;

			int dist = getDistance(C, X);

			pair<int, int> p = {location[C], C};

			for(int i = 0; i < n; i++){
				if(stype[i] == 1 && location[i] < location[C] + dist) p = max(p, {location[i], i});
			}

			if(distB[X] == distB[p.second] + ((location[C] + dist) - location[p.second])){
				location[X] = location[C] + dist;
				stype[X] = 2;
			}
			else{
				location[X] = location[B] - distB[X];
				stype[X] = 1;
				C = X;
			}
		}
	}

	sort(rght.begin(), rght.end());

	if(!rght.empty()){
		int D = rght.front().second;
 
		location[D] = location[A] + distA[D];
		stype[D] = 2;
 
		for(int i = 1; i < rght.size(); i++){
			int X = rght[i].second;
 
			int dist = getDistance(D, X);

			pair<int, int> p = {location[D], D};

			for(int i = 0; i < n; i++){
				if(stype[i] == 2 && location[i] > location[D] - dist) p = min(p, {location[i], i});
			}
 
			if(distA[X] == distA[p.second] + (location[p.second] - (location[D] - dist))){
				location[X] = location[D] - dist;
				stype[X] = 1;
			}
			else{
				location[X] = location[A] + distA[X];
				stype[X] = 2;
				D = X;
			}
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:45: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]
   45 |   for(int i = 1; i < lft.size(); i++){
      |                  ~~^~~~~~~~~~~~
rail.cpp:76: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]
   76 |   for(int i = 1; i < rght.size(); i++){
      |                  ~~^~~~~~~~~~~~~

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