Submission #106297

#	Time	Username	Problem	Language	Result	Execution time	Memory
106297		Kepperoni	Rail (IOI14_rail)	C++14	8 / 100	83 ms	512 KiB

rail

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

using namespace std;

typedef long long ll;

const ll MAXN = 5000 + 10;

ll dist[MAXN];
int ind[MAXN];

void findLocation(int N, int first, int location[], int stype[])
{
	stype[0] = 1;
	location[0] = first;
	for(int i=1; i<N; i++){
		dist[i] = getDistance(0, i);
		ind[i] = i;
	}

	sort(ind, ind+N, [](int fi, int se){return dist[fi] < dist[se];});

	int cc = 0, cd = ind[1];		
	stype[cd] = 2;
	location[cd] = first + dist[cd];

	for(int i=2; i<N; i++){
		int ci = ind[i];
		ll distc = getDistance(cc, ci);		
		ll distd = getDistance(cd, ci);		

		if(distc > distd){
			stype[ci] = 1;
			location[ci] = location[cd] - distd;
			if(distd > location[cd] - location[cc])
				cc = ci;
		} else {
			stype[ci] = 2;
			location[ci] = location[cc] + distc;
			if(distc > location[cd] - location[cc])
				cd = ci;
		}
	}
}

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