Submission #705291

#	Time	Username	Problem	Language	Result	Execution time	Memory
705291		Hacv16	Rail (IOI14_rail)	C++17	30 / 100	74 ms	516 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"

const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;

int dist[MAX][2];

void findLocation(int n, int first, int location[], int stype[]){
	int mn = INF, mnId = 0;

	for(int i = 1; i < n; i++){
		int curDist = getDistance(0, i);
		dist[i][0] = curDist;

		if(dist[i][0] < mn)
			mn = dist[i][0], mnId = i;
	}

	for(int i = 1; i < n; i++){
		int curDist = getDistance(mnId, i);	
		dist[i][1] = curDist;
	}

	location[0] = first;
	stype[0] = 1;

	location[mnId] = first + dist[mnId][0];
	stype[mnId] = 2;

	for(int i = 1; i < n; i++){
		if(i == mnId) continue;

		if(dist[i][1] < dist[i][0]){
			stype[i] = 1;
			location[i] = location[mnId] - dist[i][1];
		}else{
			stype[i] = 2;
			location[i] = location[0] + dist[i][0];
		}
 	}
}	

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