Submission #122218

#	Time	Username	Problem	Language	Result	Execution time	Memory
122218		someone_aa	Rail (IOI14_rail)	C++17	30 / 100	74 ms	716 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 5100;
ll d0[maxn], n;
ll dx[maxn];

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

	ll minval = LLONG_MAX;
	ll x = -1;
	for(int i=1;i<n;i++) {
		d0[i] = getDistance(0, i);
		if(d0[i] < minval) {
			minval = d0[i];
			x = i;
		}
	}

	for(int i=1;i<n;i++) {
		if(i == x) continue;
		dx[i] = getDistance(i, x);
	}

	location[x] = first + d0[x];
	stype[x] = 2;

	vector<pair<ll, ll> > lft, rght;
	for(int i=1;i<n;i++) {
		if(i == x) continue;

		if(d0[i] > dx[i]) {
			// either on left of x or on right

			if(d0[i] == d0[x] + dx[i]) {
				lft.pb(mp(dx[i], i));
			}
			else {
				rght.pb(mp(dx[i], i));
			}
		}
		else {
			rght.pb(mp(dx[i], i));
		}
	}

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

	if(lft.size() > 0) {
		int ind = lft[0].second;
		int dst = lft[0].first;
		stype[ind] = 1;
		location[ind] = location[x] - dst;

		int ind_limit = ind;

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

			ll temp = getDistance(ind_limit, ind);

			if(dx[ind] == dx[ind_limit] + temp) {
				// type D

				stype[ind] = 2;
				location[ind] = location[ind_limit] + temp; 
			}
			else {
				// type C
				stype[ind] = 1;
				location[ind] = location[x] - dx[ind];
				ind_limit = ind;
			}

		}
	}

	if(rght.size() > 0) {
		int ind = rght[0].second;
		int dst = d0[ind];
		stype[ind] = 2;
		location[ind] = location[0] + dst;

		int ind_limit = ind;

		for(int i=1;i<rght.size();i++) {
			ind = rght[i].second;
			dst = d0[ind];

			int temp = getDistance(ind_limit, ind);

			if(d0[ind] == d0[ind_limit] + temp) {
				// type C
				stype[ind] = 1;
				location[ind] = location[ind_limit] - temp;
			}
			else {
				// type D
				stype[ind] = 2;
				location[ind] = location[0] + d0[ind];
			}

		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<lft.size();i++) {
               ~^~~~~~~~~~~
rail.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<rght.size();i++) {
               ~^~~~~~~~~~~~

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