Submission #348837

#	Time	Username	Problem	Language	Result	Execution time	Memory
348837		dennisstar	Rail (IOI14_rail)	C++17	30 / 100	83 ms	992 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
#define gd getDistance
#define eb emplace_back
#define av(n, k) ((n)%(k)==0&&(n)>0)

using namespace std;


void findLocation(int N, int first, int L[], int T[]) {
	T[0]=1;
	L[0]=0;
	
	vector<int> D(N), S;
	int mn=(1e9), mi;
	for (int i=1; i<N; i++) {
		D[i]=gd(0, i);
		if (mn>D[i]) mn=D[i], mi=i;
	}
	T[mi]=2;
	L[mi]=mn;

	int l=0, r=mi;
	for (int i=0; i<N; i++) if (i!=l&&i!=r) S.eb(i);
	sort(S.begin(), S.end(), [&](int x, int y) { return D[x]<D[y]; });
	map<int, int> cc, dd;
	cc[L[l]]=1, dd[L[r]]=1;
	for (auto &i:S) {
		int d1=gd(l, i), d2=gd(r, i), d=L[r]-L[l];
		int im=(d1+d2-d)/2;
		if (d1<d && im<d1 && im<d2 && cc[L[l]+d1-im]) {
			int x=L[l]+d1;
			dd[x]=1;
			T[i]=2;
			L[i]=x;
		}
		else if (d1>d && av(d2-d1+d, 2) && cc[L[r]-(d2-d1+d)/2]) {
			int x=L[l]+d1;
			dd[x]=1;
			T[i]=2;
			L[i]=x;
			r=i;
		}
		else if (d2<d && im<d1 && im<d2 && dd[L[r]-d2+im]) {
			int x=L[r]-d2;
			cc[x]=1;
			T[i]=1;
			L[i]=x;
		}
		else if (d2>d && av(d1-d2+d, 2) && dd[L[l]+(d1-d2+d)/2]) {
			int x=L[r]-d2;
			cc[x]=1;
			T[i]=1;
			L[i]=x;
			l=i;
		}
		else assert(false);
	}

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

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:20:4: warning: 'mi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |  T[mi]=2;
      |    ^~

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