Submission #296292

#	Time	Username	Problem	Language	Result	Execution time	Memory
296292		nvmdava	Rail (IOI14_rail)	C++17	100 / 100	128 ms	776 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
int d[5005][3];
vector<pair<int, int> > rh, lh;

int lo[5005], st[5005];

vector<int> bruh;

void solve(int con, int flip, vector<pair<int, int> >& v){
	sort(v.begin(), v.end());
	bruh.clear();
	int r = -1;
	for(auto& x : v){

		bool ok = 0;
		int d;
		if(r == -1)
			ok = 1;
		else {
			d = lo[r] - getDistance(r, x.ss);
			if(d != 2 * (*lower_bound(bruh.begin(), bruh.end(), d)) - x.ff)
				ok = 1; 
		}

		if(ok){
			lo[r = x.ss] = x.ff;
			st[r] = 1;
			bruh.push_back(x.ff);
		} else {
			lo[x.ss] = d;
			st[x.ss] = -1;
		}
	}
	for(auto& x : v){
		st[x.ss] *= flip;
		lo[x.ss] = con + flip * lo[x.ss];
	}
}

void findLocation(int N, int first, int location[], int stype[]){
	int le, ri;
	int n = N;
	le = 0;
	int tt = 2000000;

	if(n == 1){
		location[0] = first;
		stype[0] = 1;
		return;
	}

	for(int i = 0; i < n; ++i){
		if(le == i)
			continue;
		d[i][0] = getDistance(le, i);
		if(d[i][0] < tt){
			ri = i;
			tt = d[i][0];
		}
	}
	tt = 2000000;
	for(int i = 0; i < n; ++i){
		if(ri == i) continue;
		d[i][1] = getDistance(ri, i);
		if(d[i][1] < tt){
			le = i;
			tt = d[i][1];
		}
	}
	
	lo[ri] = first + d[ri][0];
	st[ri] = 1;

	lo[le] = lo[ri] - d[le][1];
	st[le] = -1;

	d[0][0] = 2 * d[ri][0];
	d[ri][1] = 2 * d[le][1];

	for(int i = 0; i < n; ++i){
		if(le == i || ri == i) continue;

		if(d[i][0] == d[i][1] + d[ri][0])
			rh.push_back({d[i][1], i});
		else
			lh.push_back({d[i][0] - (d[ri][0] - d[le][1]), i});
	}
	solve(lo[le], 1, lh);
	solve(lo[ri], -1, rh);
	for(int i = 0; i < n; ++i){
		location[i] = lo[i];
		stype[i] = (st[i] == 1 ? 2 : 1);
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:75:26: warning: 'ri' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |  lo[ri] = first + d[ri][0];
      |                   ~~~~~~~^

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