Submission #396845

#	Time	Username	Problem	Language	Result	Execution time	Memory
396845		rainboy	Towns (IOI15_towns)	C11	35 / 100	21 ms	332 KiB

towns

#include "towns.h"

#define N	110
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int abs_(int a) { return a > 0 ? a : -a; }

unsigned int X = 12345;

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

int xx[N], yy[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 (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[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 hubDistance(int n, int sub) {
	static int ddu[N], ddv[N], ii[N];
	int u, v, i, i_, j_, d_, r_, k1, k2, k3;

	u = -1;
	for (i = 0; i < n; i++) {
		ddv[i] = i == 0 ? 0 : getDistance(0, i);
		if (u == -1 || ddv[u] < ddv[i])
			u = i;
	}
	v = -1;
	for (i = 0; i < n; i++) {
		ddu[i] = i == u ? 0 : getDistance(u, i);
		if (v == -1 || ddu[v] < ddu[i])
			v = i;
	}
	d_ = ddu[v];
	for (i = 0; i < n; i++)
		ddv[i] = i == v ? 0 : getDistance(v, i);
	r_ = INF, i_ = -1, j_ = -1;
	for (i = 0; i < n; i++) {
		int r;

		xx[i] = (d_ + ddu[i] - ddv[i]) / 2, yy[i] = (ddu[i] + ddv[i] - d_) / 2;
		r = max(xx[i], d_ - xx[i]);
		if (r_ > r)
			r_ = r, i_ = -1, j_ = -1;
		if (r_ == r) {
			if (i_ == -1 || yy[i_] == yy[i])
				i_ = i;
			else
				j_ = i;
		}
		ii[i] = i;
	}
	sort(ii, 0, n);
	k1 = 0, k2 = 0, k3 = 0;
	for (i = 0; i < n; i++)
		if (xx[i] < xx[i_])
			k1++;
		else if (xx[i] > xx[i_])
			k3++;
		else
			k2++;
	if (k1 * 2 > n || k3 * 2 > n) {
		if (j_ == -1)
			return -r_;
		i_ = j_;
		k1 = 0, k2 = 0, k3 = 0;
		for (i = 0; i < n; i++)
			if (xx[i] < xx[i_])
				k1++;
			else if (xx[i] > xx[i_])
				k3++;
			else
				k2++;
		if (k1 * 2 > n || k3 * 2 > n)
			return -r_;
	}
	return k2 * 2 <= n ? r_ : -r_;
}

Compilation message (stderr)

towns.c: In function 'rand_':
towns.c:13:18: warning: conversion to 'int' from 'unsigned int' may change the sign of the result [-Wsign-conversion]
   13 |  return (X *= 3) >> 1;
      |         ~~~~~~~~~^~~~
towns.c: In function 'hubDistance':
towns.c:37:28: warning: unused parameter 'sub' [-Wunused-parameter]
   37 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39