Submission #1013547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013547		pawned	Rail (IOI14_rail)	C++17	30 / 100	49 ms	604 KiB

rail

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "rail.h"

int N, S;

ii closeD() {	// closest D, returns {idx, pos}
	int x = -1;
	int mdist = 1e9;	// minimum distance
	int xp = -1;
	for (int i = 1; i < N; i++) {
		int dist = getDistance(0, i);
		if (dist < mdist) {
			x = i;
			xp = S + dist;
			mdist = dist;
		}
	}
	return {x, xp};
}

void findLocation(int n, int s, int location[], int stype[]) {
	N = n; S = s;
	ii pr = closeD();
	int xd = pr.fi;
	int pd = pr.se;
	location[0] = S;
	stype[0] = 1;
	location[xd] = pd;
	stype[xd] = 2;
	for (int i = 0; i < N; i++) {
		if (i == 0 || i == xd)
			continue;
		int d1 = getDistance(0, i);
		int d2 = getDistance(xd, i);
		if (d1 > d2) {	// type C
			location[i] = pd - d2;
			stype[i] = 1;
		}
		else {	// type D
			location[i] = S + d1;
			stype[i] = 2;
		}
	}
}

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