Submission #120958

#	Time	Username	Problem	Language	Result	Execution time	Memory
120958		keko37	Rail (IOI14_rail)	C++14	30 / 100	154 ms	102136 KiB

rail

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

using namespace std;

const int MAXN = 5005;
const int MAXM = 1000005;
const int INF = 1000000000;

int n, x, y, lef, rig;
int pos[MAXN], tip[MAXN];
int d[MAXN][MAXN];
vector < pair <int, int> > v;
int ima[MAXM];

//int getDistance (int x, int y) {return 1;}

void nadi (int x, int y) {
	if (d[x][y] != -1) return;
	d[x][y] = getDistance(x, y);
}

bool dodaj1 (int k) {
	pos[k] = pos[lef] + d[k][lef]; tip[k] = 2;
	if (pos[rig] < pos[k]) {
		int ofs = d[k][rig] - (pos[k] - pos[rig]);
		if (ofs < 0 || (ofs & 1)) return 0;
		int p = pos[rig] - ofs/2;
		if (ima[p] && pos[0] <= p && p < pos[rig]) return 1;
	} else if (pos[k] < pos[0]) {
		int ofs = d[k][rig] - (pos[rig] - pos[k]);
		if (ofs < 0 || (ofs & 1)) return 0;
		int p = pos[k] - ofs/2;
		if (ima[p] && pos[lef] <= p && p < pos[k]) return 1;
	}
	return 0;
}

bool dodaj2 (int k) {
	pos[k] = pos[rig] - d[k][rig]; tip[k] = 1;
	if (pos[k] < pos[lef]) {
		int ofs = d[k][lef] - (pos[lef] - pos[k]);
		if (ofs < 0 || (ofs & 1)) return 0;
		int p = pos[lef] + ofs/2;
		if (ima[p] && p <= pos[rig]) return 1;
	} else if (pos[0] < pos[k]) {
		int ofs = d[k][lef] - (pos[k] - pos[lef]);
		if (ofs < 0 || (ofs & 1)) return 0;
		int p = pos[k] + ofs/2;
		if (ima[p] && p <= pos[rig]) return 1;
	}
	return 0;
}

void findLocation (int N, int X, int location[], int stype[]) {
	n = N; x = X;
	memset(d, -1, sizeof d);
	pos[0] = x; tip[0] = 1; ima[x] = 1;
	for (int j=1; j<n; j++) {
		nadi(0, j);
		v.push_back(make_pair(d[0][j], j));
	}
	sort(v.begin(), v.end());
	y = v[0].second;
	pos[y] = x + d[0][y]; tip[y] = 2; ima[pos[y]] = 1;
	lef = 0, rig = y;
	for (auto par : v) {
		int k = par.second;
		if (k == lef || k == rig) continue;
		nadi(k, lef); nadi(k, rig);
		if (!dodaj1(k)) dodaj2(k);
		ima[pos[k]] = 1;
	}
	for (int i=0; i<n; i++) {
		location[i] = pos[i];
		stype[i] = tip[i];
	}
}

/*int main () {
    return 0;
}*/

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