Submission #548269

#	Time	Username	Problem	Language	Result	Execution time	Memory
548269		sidon	Rail (IOI14_rail)	C++17	30 / 100	76 ms	772 KiB

rail

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

void findLocation(int N, int o, int* x, int* t) {
	int d[N] {}, byD[N - 1];
	map<int, int> g;

	t[0] = g[x[0] = o] = 1;

	for(int v = 1; v < N; ++v) {
		d[v] = getDistance(0, v);
		byD[v-1] = v;
	}
	sort(byD, byD + N - 1, [&](const int &i, const int &j) {
		return d[i] < d[j];
	});

	int c = byD[0], rD = c, lD = c, rC {}, lC {};
	t[c] = g[x[c] = o + d[c]] = 2;

	for(const int &v : byD) if(v != c) {
		int z = getDistance(c, v);
		if(z > d[v]) {
			int y = getDistance(rD, v);
			int xU = (x[rD] + (o + d[v]) - y) / 2;

			if((!(((x[rD] + (o + d[v]) - y)) & 1) && g[xU] == 2)) x[v] = x[rD] - y , t[v] = 1;
			else x[rD = v] = o + d[v], t[v] = 2;
		} else {
			int y = getDistance(lC, v);
			if(!lC) x[lC = v] = x[c] - z, t[v] = 1;
			else {
				int xU = (y + x[lC]  + (x[c] - z)) / 2;
				if(!(((y + x[lC]  + (x[c] - z))) & 1) && g[xU] == 1) x[v] = x[lC] + y, t[v] = 2;
				else x[lC = v] = x[c] - z, t[v] = 1;
			}
		}
		if(t[v] == 1 && x[v] > x[rC]) rC = v;
		if(t[v] == 2 && x[v] < x[lD]) lD = v;
		g[x[v]] = t[v];
	}
}

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