제출 #282669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282669		Saboon	철로 (IOI14_rail)	C++14	100 / 100	100 ms	1016 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 10;
int dis[maxn], a[maxn];
int loc[maxn], type[maxn];
map<int,int> mp;

void findLocation(int n, int first, int location[], int stype[]){
	loc[0] = first, type[0] = 1;
	if (n == 1)
		return;
	for (int i = 1; i < n; i++)
		dis[i] = getDistance(0,i);
	for (int i = 1; i < n; i++)
		a[i] = i;
	sort(a+1, a+n, [](int a, int b){
		return dis[a] < dis[b];
	});
	loc[a[1]] = first+dis[a[1]], type[a[1]] = 2;
	int l = 0, r = a[1];
	mp[loc[0]] = 1, mp[loc[a[1]]] = 2;
	for (int _ = 2; _ < n; _++){
		int i = a[_];
		int dl = loc[l]+getDistance(l,i), dr = loc[r]-getDistance(r,i), mid = (dl+dr) / 2;
		if (mp[mid] == 1 or (mp[mid] == 0 and mid > first)){
			loc[i] = dl; 
			type[i] = 2;
			if (dl > loc[r])
				r = i;
		}
		else{
			loc[i] = dr;
			type[i] = 1;
			if (dr < loc[l])
				l = i;
		}
		mp[loc[i]] = type[i];
	}
	for (int i = 0; i < n; i++)
		location[i] = loc[i], stype[i] = type[i];
}

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