Submission #348841

#	Time	Username	Problem	Language	Result	Execution time	Memory
348841		dennisstar	Rail (IOI14_rail)	C++17	100 / 100	91 ms	876 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
#define gd getDistance
#define eb emplace_back

using namespace std;

void findLocation(int N, int first, int L[], int T[]) {
	vector<int> D(N), S;
	for (int i=1; i<N; i++) S.eb(i), D[i]=gd(0, i);
	sort(S.begin(), S.end(), [&](int x, int y) { return D[x]<D[y]; });
	
	int l=0, r=S[0];
	L[l]=0, L[r]=D[r];
	T[l]=1, T[r]=2;
	map<int, int> M;
	M[0]=1, M[D[r]]=2;

	for (int i=1; i<N-1; i++) {
		int n=S[i];
		int d1=gd(l, n), d2=gd(r, n), x=(L[l]+L[r]+d1-d2)/2;
		if (M[x]==1||(M[x]==0&&x>0)) {
			int dn=L[l]+d1;
			L[n]=dn;
			T[n]=2;
			M[dn]=2;
			if (dn>L[r]) r=n;
		}
		else {
			int dn=L[r]-d2;
			L[n]=dn;
			T[n]=1;
			M[dn]=1;
			if (dn<L[l]) l=n;
		}
	}

	for (int i=0; i<N; i++) L[i]=L[i]+first;
}

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