Submission #399525

#	Time	Username	Problem	Language	Result	Execution time	Memory
399525		bigg	Rail (IOI14_rail)	C++14	100 / 100	91 ms	716 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5100;
int dist[MAXN], v[MAXN];

int getdistance(int i, int j){
	return getDistance(i,j);
}

bool cmp(int i, int j){
	return dist[i] < dist[j];
}
map<int, int> ma;
void findLocation(int n, int first, int location[], int stype[])
{	
	location[0] = first, stype[0] = 1;
	if(n == 1) return;
	
	for(int i = 1; i < n; i++){
		dist[i] = getdistance(0,i);
	v[i] = i;
	}
	sort(v, v + n, cmp);
	int L, R;
	L = 0, R = v[1];
	
	location[R] = first + dist[R];
	stype[R] = 2;
	ma[location[L]] = 1;
	ma[location[R]] = 2; 
	for(int i = 2; i < n; i++){
		int x = v[i];
		int dL = getdistance(L,x);
		int dR = getdistance(R,x);
		int mid = (location[L] + dL + location[R] - dR)/2;
		if(ma[mid] == 1 || (ma[mid] == 0 && location[0] < mid)){
			location[x] = location[L] + dL;
			stype[x] = 2;
			if(location[x] > location[R]) R= x;
		}
		else{
			location[x] = location[R] - dR;
			stype[x] = 1;
			if(location[x] < location[L]) L = x;
		}
		ma[location[x]] = stype[x];
	}
	return;
}

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