Submission #122489

#	Time	Username	Problem	Language	Result	Execution time	Memory
122489		someone_aa	Rail (IOI14_rail)	C++17	100 / 100	109 ms	1016 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];

map<int,bool> exist_right;
map<int,bool> exist_left;

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

	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;
	exist_right[location[x]] = true;

	//cout<<"Nearest is"<<x<<" at "<<location[x]<<"\n";

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

		//cout<<i<<": "<<d0[i]<<", "<<dx[i]<<"\n";

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

	/*cout<<x<<"\n";
	cout<<"on left: \n";
	for(auto i:lft) {
		cout<<i.first<<" "<<i.second<<"\n";
	}

	cout<<"and on right\n";
	for(auto i:rght) {
		cout<<i.first<<" "<<i.second<<"\n";
	}*/

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

	//cout<<"Levo: "<<lft.size()<<" i desno: "<<rght.size()<<"\n";

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

		exist_right[location[ind]] = true;

		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);
			ll z = abs(d0[ind] - d0[ind_limit] - temp);
			z /= 2;


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

		}
	}

	if(lft.size() > 0) {
		int ind = lft[0].second;
		int dst = lft[0].first;

		stype[ind] = 1;
		location[ind] = location[x] - dst;

		exist_left[location[ind]] = true;

		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);
			ll z = abs(dx[ind] - dx[ind_limit] - temp);
			z /= 2;

//			cout<<ind<<": "<<dst<<", "<<z<<"\n";

			if(exist_left[location[ind_limit] + z]) {
				// 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;
				exist_left[location[ind]] = true;
			}
		}
	}
	//return location[x];
}

Compilation message (stderr)

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

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