제출 #1216944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216944		AmirAli_H1	Rail (IOI14_rail)	C++17	100 / 100	40 ms	8548 KiB

rail

// In the name of Allah

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

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

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 4;

int n, D, v1, v2;
int D1[maxn], D2[maxn];
vector<int> ls1, ls2;
int Dv[maxn]; pii valx[maxn];
pii res[maxn];

int getDistance(int x, int y);

void setx(int i, pii x) {
	res[i] = x;
	valx[x.F] = Mp(i, x.S);
}

bool cmp(int i, int j) {
	return (Dv[i] < Dv[j]);
}

void solvex(int v, vector<int> ls) {
	sort(all(ls), cmp);
	int vx = -1, R = ((res[v].S == 0) ? 1 : -1);
	for (int i : ls) {
		if (i == v) continue;
		if (vx == -1) {
			setx(i, Mp(res[v].F + R * Dv[i], 1 - res[v].S));
			vx = i;
			continue;
		}
		int Dx = getDistance(vx, i), w = Dv[vx] + Dx;
		if ((w - Dv[i]) % 2 == 1) {
			setx(i, Mp(res[v].F + R * Dv[i], 1 - res[v].S));
			vx = i;
		}
		else {
			int s = (w - Dv[i]) / 2;
			int lc = res[vx].F - R * s;
			if (lc >= 0 && lc < maxn && valx[lc].S == 1 - res[v].S) {
				setx(i, Mp(res[vx].F - R * Dx, 1 - res[vx].S));
			}
			else {
				setx(i, Mp(res[v].F + R * Dv[i], 1 - res[v].S));
				vx = i;
			}
		}
	}
}

void findLocation(int nx, int dx, int location[], int stype[]) {
	n = nx; D = dx;
	if (n == 1) {
		location[0] = D; stype[0] = 1;
		return ;
	}

	v1 = 0, v2 = -1;
	for (int i = 0; i < n; i++) {
		if (i == v1) D1[i] = 0;
		else {
			D1[i] = getDistance(v1, i);
			if (v2 == -1 || D1[i] < D1[v2]) v2 = i;
		}
	}
	for (int i = 0; i < n; i++) {
		if (i == v2) D2[i] = 0;
		else if (i == v1) D2[i] = D1[v2];
		else D2[i] = getDistance(v2, i);
	}

	for (int i = 0; i < n; i++) {
		if (D1[i] == D1[v2] + D2[i]) ls2.pb(i);
		else ls1.pb(i);
	}
	for (int i = 0; i < n; i++) Dv[i] = D1[i];
	fill(valx, valx + maxn, Mp(-1, -1));
	setx(v1, Mp(D, 0)); solvex(v1, ls1);
	for (int i = 0; i < n; i++) Dv[i] = D2[i];
	fill(valx, valx + maxn, Mp(-1, -1));
	setx(v2, Mp(D + D1[v2], 1)); solvex(v2, ls2);

	for (int i = 0; i < n; i++) {
		location[i] = res[i].F; stype[i] = res[i].S + 1;
	}
	return ;
}

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