Submission #1066325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066325		Mr_Husanboy	Rail (IOI14_rail)	C++17	100 / 100	93 ms	98700 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
 
template<typename T>
int len(T &a){
	return a.size();
}
 
const int maxn = 5e3;
const int inf = 1e9;
 
int memo[maxn][maxn];
 
int get(int i, int j){
	if(i == j) return 0;
	if(memo[i][j] != -1){
		return memo[i][j];
	}
	return memo[i][j] = memo[j][i] = getDistance(i, j);
}
 
void findLocation(int n, int first, int location[], int stype[])
{
	for(int i = 0; i < n; i ++){
		location[i] = -1;
		for(int j = 0; j < n; j ++){
			memo[i][j] = -1;
		}
	}
	location[0] = first;
	stype[0] = 1;
	if(n == 1){
		return;
	}
 
	vector<int> ord(n - 1);
	iota(all(ord), 1);
	sort(all(ord), [&](int i, int j){
		return get(0, i) < get(0, j);
	});
 
	int lef = 0, rig = ord[0];
	location[rig] = get(0, rig) + first;
	stype[rig] = 2;
	set<int> cs = {location[lef]}, ds = {location[rig]};
 
	auto dis = [&](pair<int,int> a, pair<int,int> b)->int{
		if(a.ff == b.ff) return 0;
		if(a.ff > b.ff) swap(a, b);
		if(a.ss == 1 && b.ss == 2){
			return b.ff - a.ff;
		}
 
		if(a.ss == 1 && b.ss == 1){
			auto it = ds.lower_bound(b.ff);
			if(it == ds.end()){
				return inf;
			}
			return *it - a.ff + *it - b.ff;
		}
 
		if(a.ss == 2 && b.ss == 2){
			auto it = cs.upper_bound(a.ff);
			if(it == cs.begin()){
				return inf;
			}
			-- it;
			return a.ff - *it + b.ff - *it;
		}
 
		auto l = cs.upper_bound(a.ff);
		auto r = ds.lower_bound(b.ff);
		if(l == cs.begin() || r == ds.end()) return inf;
		-- l;
		return a.ff - *l + *r - *l + *r - b.ff;
	};
 
	for(auto _ = 1;  _ < n - 1; _ ++){
		int i = ord[_];
		//cout << i << ' ';
		int x = -1, t = -1;
	{
		int pos = get(lef, i) + location[lef];
		//cout << dis({pos, 2}, {location[lef], 1}) << endl;
		if(dis({pos, 2}, {location[lef], 1}) == get(lef, i) && dis({pos, 2}, {first, 1}) == get(0, i) && dis({pos, 2}, {location[rig], 2}) == get(rig, i)){
			x = pos;
			t = 2;
		}
	}
	{
		int pos = location[rig] - get(rig, i);
		if(dis({pos, 1}, {location[rig], 2}) == get(rig, i) && dis({pos, 1}, {first, 1}) == get(0, i) && dis({pos, 2}, {location[lef], 1}) == get(lef, i)){
			x = pos;
			t = 1;
		}
	}
		if(x == -1){
		{
			int pos = get(lef, i) + location[lef];
			if(dis({pos, 2}, {location[lef], 1}) == get(lef, i) && dis({pos, 2}, {first, 1}) == get(0, i)){
				x = pos;
				t = 2;
			}
		}
		{
			int pos = location[rig] - get(rig, i);
			if(dis({pos, 1}, {location[rig], 2}) == get(rig, i) && dis({pos, 1}, {first, 1}) == get(0, i)){
				x = pos;
				t = 1;
			}
		}
		}
 
		location[i] = x;
		stype[i] = t;
		if(stype[i] == 1){
			if(location[lef] > location[i]){
				lef = i;
			}
			cs.insert(location[i]);
		}else{
			if(location[rig] < location[i]){
				rig = i;
			}
			ds.insert(location[i]);
		}
		//cout << x << endl;
	}
}

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