Submission #106483

#	Time	Username	Problem	Language	Result	Execution time	Memory
106483		tincamatei	Rail (IOI14_rail)	C++14	30 / 100	87 ms	604 KiB

rail

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

using namespace std;

const int MAX_N = 5000;

enum RailType {
	C,
	D
};

struct Station {
	int dist1, dist2;
	int block;
	RailType type;
} v[MAX_N];

vector<int> toright, toleft;
int *location, *stype;

bool cmp1(int a, int b) {
	return v[a].dist1 < v[b].dist1;
}

bool cmp2(int a, int b) {
	return v[a].dist2 < v[b].dist2;
}

void findLocation(int N, int first, int _location[], int _stype[]) {
	int left = 0, right = 1;

	location = _location;
	stype = _stype;

	v[0].block = first;
	v[0].type = C;

	if(N > 1) {
		// get next D rail
		for(int i = 1; i < N; ++i) {
			v[i].dist1 = getDistance(left, i);
			if(v[i].dist1 < v[right].dist1)
				right = i;
		}

		v[right].block = v[left].block + v[right].dist1;
		v[right].type = D;
		v[left].dist2 = v[right].dist1;

		// get distances to right
		// also find previous C rail from right
		for(int i = 0; i < N; ++i) {
			if(i != right && i != left) {
				v[i].dist2 = getDistance(right, i);
				if(v[i].dist2 < v[left].dist2)
					left = i;
			}
		}
		
		v[left].block = v[right].block - v[left].dist2;
		v[left].type = C;

		for(int i = 0; i < N; ++i)
			v[i].dist1 -= (v[left].block - first);
		v[0].dist1 = v[right].block - first + v[right].block - v[left].block;
		v[left].dist1 = 0;
		
		for(int i = 0; i < N; ++i)
			if(i != left && i != right && v[i].dist1 < v[i].dist2)
				toright.push_back(i);
			else if(i != left && i != right)
				toleft.push_back(i);
		
		sort(toright.begin(), toright.end(), cmp1);
		sort(toleft.begin(), toleft.end(), cmp2);

		int aux = right;
		for(auto it: toright) {
			int poz1, poz2, x;
			poz2 = v[left].block + v[it].dist1;
			poz1 = v[aux].block - (v[it].dist1 - (v[aux].block - v[left].block));
			x = getDistance(aux, it);
			
			if(x == v[aux].block - poz1) {
				v[it].type = C;
				v[it].block = poz1;
			} else {
				v[it].type = D;
				v[it].block = poz2;
				aux = it;
			}
		}

		aux = left;
		for(auto it: toleft) {
			int poz1, poz2, x;
			poz2 = v[right].block - v[it].dist2;
			poz1 = v[aux].block + (v[it].dist2 - (v[right].block - v[aux].block));
			x = getDistance(aux, it);

			if(x == poz1 - v[aux].block) {
				v[it].type = D;
				v[it].block = poz1;
			} else {
				v[it].type = C;
				v[it].block = poz2;
				aux = it;
			}
		}
	}

	for(int i = 0; i < N; ++i) {
		location[i] = v[i].block;
		stype[i] = v[i].type + 1;
	}
}

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