oj.uz

Submission #391776

# Submission time Handle Problem Language Result Execution time Memory
391776 2021-04-19T18:58:04 Z rainboy Rail (IOI14_rail) C
100 / 100
 98 ms 564 KB 
#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;
	}
}

int found(int *xx, int *tt, int *ii, int n, int x, int t) {
	int i;

	for (i = 0; i < n; i++)
		if (xx[ii[i]] == x)
			return tt[ii[i]] == t;
	return 0;
}

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] - dd[ii1[0]];
	for (i = 1; i < n1; i++) {
		int i_ = ii1[i], d = getDistance(l, i_), x = xx[l] + (dd[l] + d - dd[i_]) / 2;

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

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

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 1 ms 216 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 0 ms 216 KB Output is correct
10 Correct 1 ms 216 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 556 KB Output is correct
2 Correct 89 ms 428 KB Output is correct
3 Correct 88 ms 432 KB Output is correct
4 Correct 88 ms 432 KB Output is correct
5 Correct 93 ms 440 KB Output is correct
6 Correct 94 ms 564 KB Output is correct
7 Correct 91 ms 464 KB Output is correct
8 Correct 89 ms 432 KB Output is correct
9 Correct 93 ms 448 KB Output is correct
10 Correct 91 ms 464 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 444 KB Output is correct
2 Correct 89 ms 452 KB Output is correct
3 Correct 89 ms 432 KB Output is correct
4 Correct 89 ms 444 KB Output is correct
5 Correct 91 ms 444 KB Output is correct
6 Correct 98 ms 448 KB Output is correct
7 Correct 95 ms 448 KB Output is correct
8 Correct 89 ms 436 KB Output is correct
9 Correct 89 ms 464 KB Output is correct
10 Correct 89 ms 460 KB Output is correct
11 Correct 90 ms 444 KB Output is correct
12 Correct 92 ms 528 KB Output is correct
13 Correct 89 ms 448 KB Output is correct
14 Correct 90 ms 444 KB Output is correct
15 Correct 92 ms 468 KB Output is correct
16 Correct 89 ms 444 KB Output is correct
17 Correct 91 ms 448 KB Output is correct
18 Correct 92 ms 548 KB Output is correct
19 Correct 90 ms 444 KB Output is correct
20 Correct 91 ms 436 KB Output is correct