Submission #57910

#	Time	Username	Problem	Language	Result	Execution time	Memory
57910		aome	철로 (IOI14_rail)	C++17	0 / 100	93 ms	1212 KiB

rail

#include "rail.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 5005;

int dis[2][N];

void findLocation(int n, int first, int location[], int stype[]) {
	location[0] = first, stype[0] = 1;
	for (int i = 1; i < n; ++i) {
		dis[0][i] = getDistance(0, i);
	}
	int p1 = 1;
	for (int i = 2; i < n; ++i) {
		if (dis[0][p1] > dis[0][i]) p1 = i;
	}
	location[p1] = location[0] + dis[0][p1], stype[p1] = 2;
	vector<int> vecl, vecr;
	for (int i = 1; i < n; ++i) {
		if (i == p1) continue;
		dis[1][i] = getDistance(p1, i);
		if (dis[1][i] <= dis[0][p1]) {
			location[i] = location[p1] - dis[1][i], stype[i] = 1;
		}
		else {
			if (dis[p1][i] == dis[0][i] + dis[0][p1]) vecr.push_back(i);
			else vecl.push_back(i);
		}
	}
	sort(vecl.begin(), vecl.end(), [&] (int x, int y) {
		return dis[1][x] < dis[1][y];
	});
	sort(vecr.begin(), vecr.end(), [&] (int x, int y) {
		return dis[0][x] < dis[0][y];
	});
	int cur;
	vector<int> vec;
	{	
		cur = p1;
		vec.clear();
		vec.push_back(p1);
		for (auto i : vecr) {
			int tmp1 = getDistance(cur, i);
			int tmp2 = dis[0][i] + location[0];
			int tmp3 = tmp2 - tmp1;
			int p = -1;
			for (auto j : vec) {
				if (location[j] >= tmp3) p = j;
			}
			if (tmp2 - location[p] == location[p] - tmp3) {
				location[i] = tmp3, stype[i] = 1;
			}
			else {
				location[i] = tmp2, stype[i] = 2, vec.push_back(i);
			}
		}
	}
	{
		cur = 0;
		vec.clear();
		vec.push_back(0);
		for (auto i : vecl) {
			int tmp1 = getDistance(cur, i);
			int tmp2 = location[1] - dis[1][i];
			int tmp3 = tmp2 + tmp1;
			int p = -1;
			for (auto j : vec) {
				if (location[j] <= tmp3) p = j;
			}
			if (tmp2 - location[p] == location[p] - tmp3) {
				location[i] = tmp3, stype[i] = 2;
			}
			else {
				location[i] = tmp2, stype[i] = 1, vec.push_back(i);
			}
		}
	}
}

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