Submission #391465

#	Time	Username	Problem	Language	Result	Execution time	Memory
391465		rainboy	Rail (IOI14_rail)	C11	30 / 100	90 ms	388 KiB

rail

#include "rail.h"

#define N	5000
#define INF	0x3f3f3f3f

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int dd[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (dd[ii[j]] == dd[i_])
				j++;
			else if (dd[ii[j]] < dd[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

void findLocation(int n, int x0, int xx[], int tt[]) {
	static int ii1[N], ii2[N];
	int n1, n2, i, ir, d_, l, r;

	d_ = INF, ir = -1;
	for (i = 1; i < n; i++) {
		dd[i] = getDistance(0, i);
		if (d_ > dd[i])
			d_ = dd[i], ir = i;
	}
	n1 = n2 = 0;
	for (i = 0; i < n; i++) {
		int d = getDistance(ir, i);

		if (i == 0 || i != ir && d_ + d == dd[i])
			dd[i] = d, ii1[n1++] = i;
		else
			ii2[n2++] = i;
	}
	tt[0] = 1, xx[0] = x0, tt[ir] = 2, xx[ir] = x0 + d_;
	sort(ii1, 0, n1);
	l = ii1[0], r = ir;
	tt[ii1[0]] = 1, xx[ii1[0]] = xx[r] - getDistance(r, ii1[0]);
	for (i = 1; i < n1; i++) {
		int i_ = ii1[i], d = getDistance(r, i_), d_;

		if (d == dd[i_] - (xx[ir] - xx[r])) {
			d_ = getDistance(l, i_);
			if (d_ < xx[r] - xx[l])
				tt[i_] = 2, xx[i_] = xx[l] + d_, r = i_;
			else
				tt[i_] = 1, xx[i_] = xx[r] - d, l = i_;
		} else
			tt[i_] = 2, xx[i_] = xx[l] + (d - (xx[r] - xx[l]));
	}
	sort(ii2, 0, n2);
	l = 0, r = ii2[0];
	tt[ii2[0]] = 2, xx[ii2[0]] = xx[l] + getDistance(l, ii2[0]);
	for (i = 1; i < n2; i++) {
		int i_ = ii2[i], d = getDistance(l, i_), d_;

		if (d == dd[i_] - (xx[l] - xx[0])) {
			d_ = getDistance(r, i_);
			if (d_ < xx[r] - xx[l])
				tt[i_] = 1, xx[i_] = xx[r] - d_, l = i_;
			else
				tt[i_] = 2, xx[i_] = xx[l] + d, r = i_;
		} else
			tt[i_] = 1, xx[i_] = xx[r] - (d - (xx[r] - xx[l]));
	}
}

Compilation message (stderr)

rail.c: In function 'findLocation':
rail.c:47:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   47 |   if (i == 0 || i != ir && d_ + d == dd[i])
      |                 ~~~~~~~~^~~~~~~~~~~~~~~~~~

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