Submission #132456

#	Time	Username	Problem	Language	Result	Execution time	Memory
132456		Sorting	Rail (IOI14_rail)	C++14	30 / 100	84 ms	504 KiB

rail

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

using namespace std;

const int inf = 1e9;

const int N = 5007;

int getDistance(int i, int j);

int d[N][N];

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

	int mn = inf, x = 0;

	for(int i = 1; i < n; i++){
		d[0][i] = getDistance(0, i);
		mn = min(mn, d[0][i]);
		if(mn == d[0][i]){
			x = i;
		}
	}

	for(int i = 1; i < n; i++){
		if(i == x){
			stype[i] = 2;
			location[i] = first + mn;
			continue;
		}

		if(getDistance(i, x) == d[0][i] - mn){
			stype[i] = 1;
			location[i] = first - (d[0][i] - 2 * mn);
		}
		else{
			stype[i] = 2;
			location[i] = first + d[0][i];
		}
	}
}

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