제출 #652541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652541		ymm	철로 (IOI14_rail)	C++17	100 / 100	74 ms	844 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,
};

map<int, int> mp;

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);
	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);
	}
	from_1[mn] = from_0[0];
	sort(lefty.begin(), lefty.end());
	sort(wright.begin(), wright.end());
	assert(lefty.size());
	int rD = mn, lC = lefty.front().second;
	lefty.erase(lefty.begin());
	location[mn] = first + from_0[mn];
	stype[mn] = D;
	mp[location[mn]] = D;
	location[lC] = location[mn] - from_1[lC];
	stype[lC] = C;
	mp[location[lC]] = C;
	for (auto [_, i] : wright) {
		int disr = getDistance(rD, i);
		int locD = first + from_0[i];
		int locC = location[rD] - disr;
		int locX = (locC + locD)/2;
		if (mp[locX] != D) {
			stype[i] = D;
			location[i] = locD;
			mp[location[i]] = D;
			rD = i;
		} else {
			stype[i] = C;
			location[i] = locC;
			mp[location[i]] = C;
		}
	}
	for (auto [_, i] : lefty) {
		int disl = getDistance(lC, i);
		int locC = location[mn] - from_1[i];
		int locD = location[lC] + disl;
		int locX = (locC + locD)/2;
		if (mp[locX] != C) {
			stype[i] = C;
			location[i] = locC;
			mp[location[i]] = C;
			lC = i;
		} else {
			stype[i] = D;
			location[i] = locD;
			mp[location[i]] = D;
		}
	}
}

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