Submission #130940

#	Time	Username	Problem	Language	Result	Execution time	Memory
130940		MAMBA	Rail (IOI14_rail)	C++17	30 / 100	175 ms	636 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;
bitset<5050> mark;

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];
			if (!mark[e]) {
				stype[e] = 1;
				location[e] = location[ONE] - dist[1][e];
				rep(j , i + 1 , le.size())
					if (getDistance(le[j] , e) + dist[1][e] == dist[1][le[j]]) {
						mark[le[j]] = true;
						stype[le[j]] = 2;
						location[le[j]] = location[e] + dist[1][le[j]] - dist[1][e];
					}
			}
		}
	}

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

		}

	}


	return;
}

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