Submission #130917

#	Time	Username	Problem	Language	Result	Execution time	Memory
130917		MAMBA	Rail (IOI14_rail)	C++17	30 / 100	85 ms	632 KiB

rail

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

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define all(x) x.begin(),x.end()

int dist[2][5010];
vector<int> le, ri;

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

	rep(i , 1 , N)
		dist[0][i] = getDistance(0 , i);
	
	int ONE = min_element(dist[0] + 1 , dist[0] + N) - dist[0];
	location[ONE] = first + dist[0][ONE];
	stype[ONE] = 2;

	rep(i , 0 , N)
		dist[1][i] = getDistance(i , ONE);

	le.pb(0);
	rep(i , 1 , N)
		if (i != ONE) {
			if (dist[0][i] > dist[1][i])
				le.pb(i);
			else 
				ri.pb(i);
		}

	{
		sort(all(le) , [](int a , int b) { return dist[1][a] < dist[1][b]; });
		int last = le[0];
		location[last] = location[ONE] - dist[1][last];
		stype[last] = 1;
		rep(i ,1 , le.size()) {
			int e = le[i];
			int me = getDistance(last , e);
			if (me != dist[1][e] - dist[1][last]) {
				last = e;
				stype[last] = 1;
				location[last] = location[ONE] - dist[1][last];
			}
			else {
				stype[e] = 2;
				location[e] = location[last] + me;
			}
		}
	}

	{
		sort(all(ri) , [](int a, int b) { return dist[0][a] < dist[0][b]; });
		int last = ONE;
		rep(i , 0 , ri.size()) {
			int e = ri[i];
			int me = getDistance(last , e);
			if (me != dist[0][e] - dist[0][last]) {
				last = e;
				stype[last] = 2;
				location[last] = location[0] + dist[0][last];
			}
			else {
				stype[e] = 1;
				location[e] = location[last] - me;
			}
		}

	}



	return;
}

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