Submission #121559

#	Time	Username	Problem	Language	Result	Execution time	Memory
121559		WhipppedCream	Rail (IOI14_rail)	C++17	100 / 100	95 ms	4476 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int n;

const int maxn = 5005;

int dist0[maxn];
int distu[maxn];

const int maxs = 4e6+5;

int typ[maxs];

bool cmp1(int a, int b)
{
	return dist0[a]< dist0[b];
}

bool cmp2(int a, int b)
{
	return distu[a]< distu[b];
}

void findLocation(int N, int first, int location[], int stype[])
{
	location[0] = first;
	typ[first] = 1;
	stype[0] = 1;
	n = N;
	ii near = {1e9, 0};
	for(int i = 1; i< N; i++)
	{
		dist0[i] = getDistance(0, i);
		near = min(near, {dist0[i], i});
	}
	int u = near.Y;
	location[u] = first+dist0[u];
	stype[u] = 2;
	typ[location[u]] = 2;
	distu[0] = dist0[u];
	vector<int> tol, tor;
	// printf("u = %d\n", u);
	for(int i = 1; i< N; i++)
	{
		if(i == u) continue;
		distu[i] = getDistance(u, i);
		if(dist0[i] == dist0[u]+distu[i])
		{
			if(distu[i]< dist0[u])
			{
				tor.pb(i);
			}
			else tol.pb(i);
		}
		else tor.pb(i);
	}
	sort(tor.begin(), tor.end(), cmp1);
	int y = u;
	for(int z : tor)
	{
		int k = dist0[z]-dist0[y]-getDistance(y, z);
		k = -k;
		k /= 2;
		// printf("for %d to be type 1 there must be 2 at %d\n", z, location[y]-k); 
		if(typ[location[y]-k] == 2)
		{
			//type c
			int mid = location[y]-k;
			assert(dist0[z]> mid-first);
			location[z] = mid-(dist0[z]-(mid-first));
			// printf("location[%d] = %d\n", z, location[z]);
			typ[location[z]] = 1;
			stype[z] = 1;
		}
		else
		{
			//type d
			location[z] = first+dist0[z];
			typ[location[z]] = 2;
			stype[z] = 2;
			y = z;
		}
	}
	y = 0;
	sort(tol.begin(), tol.end(), cmp2);
	for(int z : tol)
	{
		int k = distu[z]-distu[y]-getDistance(y, z);
		k = -k;
		k /= 2;
		if(typ[location[y]+k] == 1)
		{
			//type d
			int mid = location[y]+k;
			location[z] = mid+(distu[z]-(location[u]-mid));
			typ[location[z]] = 2;
			stype[z] = 2;
		}
		else
		{
			//type c
			location[z] = location[u]-distu[z];
			typ[location[z]] = 1;
			stype[z] = 1;
			y = z;
		}
	}
	// for(int i = 0; i< n; i++) printf("%d %d\n", stype[i], location[i]);
}

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