Submission #791747

#	Time	Username	Problem	Language	Result	Execution time	Memory
791747		NothingXD	Rail (IOI14_rail)	C++17	100 / 100	82 ms	568 KiB

rail

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef complex<double> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e3 + 10;

int n, h[maxn][2], idx[maxn];

bool cmp(int x, int y){
	return h[x][0] < h[y][0];
}

void findLocation(int N, int first, int loc[], int type[]){
	n = N;
	for (int i = 1; i < n; i++){
		h[i][0] = getDistance(0, i);
		idx[i] = i;
	}
	sort(idx, idx + n, cmp);
	h[0][1] = h[idx[1]][0];
	for (int i = 1; i < n; i++){
		if (i == idx[1]) continue;
		h[i][1] = getDistance(idx[1], i);
	}
	loc[0] = first;
	loc[idx[1]] = first + h[idx[1]][0];
	type[0] = 1;
	type[idx[1]] = 2;
	int l = 0, r = idx[1];
	for (int i = 2; i < n; i++){
		if (h[idx[1]][0] + h[idx[i]][1] == h[idx[i]][0]){
			if (h[idx[i]][1] <= h[idx[1]][0]){
				type[idx[i]] = 1;
				loc[idx[i]] = loc[idx[1]] - h[idx[i]][1];
				continue;
			}
			int dis = getDistance(l, idx[i]);
			int tmp = (dis + h[idx[i]][1] - h[l][1]) / 2;
			tmp = dis - tmp;
			tmp += loc[l];
			bool flg = true;
			for (int j = 0; j < i; j++){
				if (loc[idx[j]] == tmp && type[idx[j]] == 1) flg = false;
			}
			if (flg){
				loc[idx[i]] = loc[idx[1]] - h[idx[i]][1];
				type[idx[i]] = 1;
				l = idx[i];
			}
			else{
				loc[idx[i]] = loc[l] + dis;
				type[idx[i]] = 2;
			}
			continue;
		}
		int dis = getDistance(r, idx[i]);
		int tmp = (dis + h[idx[i]][0] - h[r][0]) / 2;
		tmp = dis - tmp;
		tmp = loc[r] - tmp;
		bool flg = true;
		for (int j = 0; j < i; j++){
			if (loc[idx[j]] == tmp && type[idx[j]] == 2) flg = false;
		}
		if (flg){
			loc[idx[i]] = loc[idx[0]] + h[idx[i]][0];
			type[idx[i]] = 2;
			r = idx[i];
		}
		else{
			loc[idx[i]] = loc[r] - dis;
			type[idx[i]] = 1;
		}
	}
}

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