Submission #603319

#	Time	Username	Problem	Language	Result	Execution time	Memory
603319		farhan132	Rail (IOI14_rail)	C++17	100 / 100	113 ms	98804 KiB

rail

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

using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert


const ll N = 5005;

ll dist[N][N];

ll D_(ll i, ll j){
	if(i == j) return 0;
	if(dist[i][j] != -1) return dist[i][j];
	dist[i][j] = dist[j][i] = getDistance(i, j);
	return dist[i][j];
}

void findLocation(int n, int first, int location[], int stype[]){

	memset(dist, -1, sizeof(dist));

	ii mn = {1e9, 0};
	location[0] = first; stype[0] = 1;
	if(n == 1) return;

	vector < ll > all;
	set < ii > C,D;

	for(ll i = 1; i < n; i++){
		all.pb(i);
	}
	sort(all.begin(), all.end(),[&](ll i, ll j){
		return D_(0, i) < D_(0, j);
	});

	C.in({first, 0});
	D.in({first + D_(0, all[0]), all[0]});
	ll l = 0, r = all[0];
	location[r] = first + D_(l, r);
	stype[r] = 2;

	for(auto i : all){
		if(i == r) continue;
		// L i R (C)
		ll x = D_(l, i);
		ll y = D_(r, i);
		ll ex = location[r] - y;
		if(ex >= first){
			auto [pos, j] = *D.lower_bound({ex, 0} );
			if(pos != ex && x == pos - location[l] + pos - ex){
				location[i] = ex;
				stype[i] = 1; // C
				C.in({location[i], i});
				continue;
			}
		}
		// L i R (D)
		ex = location[l] + x;
		if(ex <= first){
			auto [pos, j] = *(--C.upper_bound({ex, 1e9}));
			if(pos != ex && y == location[r] - pos + ex - pos){
				location[i] = ex;
				stype[i] = 2; // D
				D.in({location[i], i});
				continue;
			}
		}
			// L R i
			ll ex1 = location[l] + x;
			ll ex2 = location[r] - y;
			if((ex1 == location[0] + D_(0, i) && ex1 > location[r]) && (ex2 < location[l] && D_(0, i) == 2*location[all[0]] - location[0] - ex2)){
				location[i] = ex2;
				stype[i] = 1; // C
				C.in({location[i], i});
				l = i;
			}else if(ex1 == location[0] + D_(0, i) && ex1 > location[r]){
				location[i] = ex1;
				stype[i] = 2; // D
				D.in({location[i], i});
				r = i;
			}else{
				location[i] = ex2;
				stype[i] = 1; // C
				C.in({location[i], i});
				l = i;
			}
	}


	return;

}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:30:5: warning: variable 'mn' set but not used [-Wunused-but-set-variable]
   30 |  ii mn = {1e9, 0};
      |     ^~

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