Submission #741533

#	Time	Username	Problem	Language	Result	Execution time	Memory
741533		baojiaopisu	Rail (IOI14_rail)	C++14	30 / 100	91 ms	568 KiB

rail

#include "rail.h"
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const int N = 1e5 + 10;

int a[N], b[N];

void findLocation(int n, int first, int location[], int skype[]) {
	for(int i = 0; i < n; i++) skype[i] = 0;

	location[0] = first;
	skype[0] = 1;

	int pos = 0, D = 100000000;
	for(int i = 1; i < n; i++) {
		int x = getDistance(0, i);
		if(!pos) {
			pos = i;
			D = x;
		} else {
			if(D > x) {
				D = x;
				pos = i;
			}
		}
		a[i] = x;
	}

	location[pos] = first + D;
	skype[pos] = 2;

	for(int i = 1; i < n; i++) {
		if(i == pos) continue;
		int x = getDistance(i, pos);
		if(x < a[pos]) {
			location[i] = location[pos] - x;
			skype[i] = 1;
		}
		b[i] = x;
	}

	vector<int> left, right;
	for(int i = 1; i < n; i++) {
		if(i == pos) continue;
		if(a[i] > b[i]) left.pb(i);
		else right.pb(i);
	}

	sort(left.begin(), left.end(), [&](int x, int y) {
		return b[x] < b[y];
	});

	sort(right.begin(), right.end(), [&](int x, int y) {
		return a[x] < a[y];
	});

	vector<int> open;
	for(int i = 0; i < left.size(); i++) {
		int curr = left[i];
		if(i == 0) {
			open.pb(curr);
			location[curr] = location[pos] - b[curr];
			skype[curr] = 1;
			continue;
		}

		int x = getDistance(open.back(), curr);
		location[curr] = location[open.back()] + x;
		bool ok = (location[curr] < location[0]);
		for(int j = 0; j < n; j++) ok &= (location[curr] != location[j]);
		if(!ok) {
			location[curr] = location[pos] - b[curr];
			open.pb(curr);
			skype[curr] = 1;
			continue;
		}

		int np = 0;
		for(int j = open.size() - 1; j >= 0; j--) {
			if(location[open[j]] < location[pos]) np = j;
		}

		int t = getDistance(open[np], pos);
		if(t + location[pos] - location[open[np]] == b[curr]) continue;
		location[curr] = location[pos] - b[curr];
		open.pb(curr);
		skype[curr] = 1;
	}	

	vector<int> close;
	for(int i = 0; i < right.size(); i++) {
		int curr = right[i];
		if(i == 0) {
			close.pb(curr);
			location[curr] = location[0] + a[curr];
			skype[curr] = 2;
			continue;
		}

		int x = getDistance(close.back(), curr);
		location[curr] = location[close.back()] - x;
		bool ok = (location[curr] > location[pos]);
		for(int j = 0; j < n; j++) ok &= (location[curr] != location[j]);
		if(!ok) {
			location[curr] = location[0] + a[curr];
			close.pb(curr);
			skype[curr] = 2;
			continue;
		}

		int np = 0;
		for(int j = close.size() - 1; j >= 0; j--) {
			if(location[close[j]] > location[pos]) np = j;
		}

		int t = getDistance(close[np], pos);
		if(t + location[close[np]] - location[0] == a[curr]) continue;
		location[curr] = location[0] + a[curr];
		close.pb(curr);
		skype[curr] = 2;
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < left.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
rail.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 0; i < right.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~

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