제출 #652538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652538		ymm	철로 (IOI14_rail)	C++17	30 / 100	78 ms	504 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 5010;
int from_0[N];
int from_1[N];
vector<pii> lefty;
vector<pii> wright;
int n;

enum {
	C = 1,
	D = 2,
};

void findLocation(int _N, int first, int location[], int stype[])
{
	n = _N;
	int mn = 1;
	Loop (i,1,n) {
		from_0[i] = getDistance(0, i);
		if (from_0[i] < from_0[mn])
			mn = i;
	}
	int X, Y = 1e9+10;
	Loop (i,0,n) {
		if (i == mn)
			continue;
		from_1[i] = getDistance(mn, i);
		if (from_1[i] < Y)
			Y = from_1[i];
	}
	X = from_0[mn] - Y;
	from_0[0] = 2*(X+Y);
	cerr << "mn = " << mn << '\n';
	Loop (i,0,n) {
		if (i == mn)
			continue;
		if (from_0[i] - from_1[i] == X-Y)
			wright.push_back({from_1[i], i});
		else if (from_0[i] - from_1[i] == X+Y)
			lefty.push_back({from_1[i], i});
		else
			assert(false);
	}
	sort(lefty.begin(), lefty.end());
	sort(wright.begin(), wright.end());
	assert(lefty.size());
	int rD = mn, rC = lefty.front().second;
	int lD = mn, lC = lefty.front().second;
	lefty.erase(lefty.begin());
	location[mn] = first + from_0[mn];
	stype[mn] = D;
	location[lC] = location[mn] - from_1[lC];
	stype[lC] = C;
	for (auto [_, i] : wright) {
		int disr = getDistance(rD, i);
		int locD = location[0] + from_0[i];
		cerr << location[rD] + locD - 2*location[rC] << '\n';
		if (disr == location[rD] + locD - 2*location[rC]) {
			stype[i] = D;
			location[i] = locD;
			rD = i;
		} else {
			stype[i] = C;
			location[i] = location[rD] - disr;
			if (location[i] > location[rC])
				rC = i;
		}
	}
	for (auto [_, i] : lefty) {
		int disl = getDistance(lC, i);
		int locC = location[mn] - from_1[i];
		if (disl == 2*location[lD] - location[lC] - locC) {
			stype[i] = C;
			location[i] = locC;
			lC = i;
		} else {
			stype[i] = D;
			location[i] = location[lC] + disl;
			if (location[i] < location[lD])
				lD = i;
		}
	}
}

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