Submission #49518

#	Time	Username	Problem	Language	Result	Execution time	Memory
49518		Namnamseo	Rail (IOI14_rail)	C++17	8 / 100	112 ms	19440 KiB

rail

#include "rail.h"

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

using pp=pair<int,int>;
#define x first
#define y second
pp kyori[5010];

int dc[5010][5010];

int dst(int a, int b){
	if(dc[a][b]) return dc[a][b];
	return dc[a][b]=getDistance(a, b);
}

void findLocation(int n, int first, int location[], int stype[])
{
	for(int i=1; i<n; ++i) kyori[i-1]={dst(0, i), i};
	sort(kyori, kyori+n-1);
	int L = 0, Lp = first, R = kyori[0].y, Rp = Lp + kyori[0].x;
	location[L] = Lp;
	location[R] = Rp;
	stype[L] = 1; stype[R] = 2;
	for(int i=1; i<n-1; ++i){
		int j = kyori[i].y;
		int dl = dst(L, j), dr = dst(R, j);
		int jp;
		if(dl + (Rp-Lp) == dr){
			jp = Lp + dl;
			stype[j] = 2;
			if(jp > Rp){
				R = j;
				Rp = jp;
			}
		} else {
			jp = Rp - dr;
			stype[j] = 1;
			if(jp < Lp){
				L = j;
				Lp = jp;
			}
		}
		location[j] = jp;
	}
}

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