Submission #905205

#	Time	Username	Problem	Language	Result	Execution time	Memory
905205		rainboy	Power plants (CPSPC17_power)	C11	100 / 100	710 ms	6828 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3fLL

unsigned int Z = 12345;

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

int xx[N], yy[N], ii[N], 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) {
			int c = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[ii[j]] - yy[i_];

			if (c == 0)
				j++;
			else if (c < 0) {
				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 zz[N + 1], ll[N + 1], rr[N + 1], ii_[N + 1], _, u_, l_, r_;

int node(int i) {
	zz[_] = rand_();
	ll[_] = rr[_] = 0;
	ii_[_] = i;
	return _++;
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = yy[ii_[u]] != yy[i] ? yy[ii_[u]] - yy[i] : ii_[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

void tr_add(int i) {
	split(u_, i);
	u_ = merge(merge(l_, node(i)), r_);
}

void tr_remove(int i) {
	split(u_, i);
	u_ = merge(l_, r_);
}

int ds[N * 2];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

int join_(int i, int j) {
	if (find(i << 1 | 0) == find(j << 1 | 0))
		return 0;
	join(i << 1 | 0, j << 1 | 1), join(i << 1 | 1, j << 1 | 0);
	return 1;
}

int join1(int u, int j, long long d) {
	int x, y;

	if (u == 0)
		return 1;
	x = xx[ii_[u]] - xx[j], y = yy[ii_[u]] - yy[j];
	if ((long long) y * y >= d)
		return join1(y < 0 ? rr[u] : ll[u], j, d);
	else {
		if ((long long) x * x + (long long) y * y < d && !join_(ii_[u], j))
			return 0;
		return join1(ll[u], j, d) && join1(rr[u], j, d);
	}
}

int solve(long long d, int print) {
	static int ii0[N], ii1[N];
	int n0, n1, h, h_, i, j, x;

	_ = 1, u_ = 0;
	memset(ds, -1, n * 2 * sizeof *ds);
	for (h = 0, h_ = 0; h_ < n; h_++) {
		j = ii[h_];
		while (1) {
			i = ii[h], x = xx[j] - xx[i];
			if ((long long) x * x < d)
				break;
			tr_remove(i), h++;
		}
		if (!join1(u_, j, d))
			return 0;
		tr_add(ii[h_]);
	}
	if (print) {
		n0 = n1 = 0;
		for (i = 0; i < n; i++)
			if (find(i << 1 | 0) < find(i << 1 | 1))
				ii0[n0++] = i;
			else
				ii1[n1++] = i;
		printf("%lld\n", d);
		printf("%d\n", n0);
		for (i = 0; i < n0; i++)
			printf("%d ", ii0[i] + 1);
		printf("\n");
		printf("%d\n", n1);
		for (i = 0; i < n1; i++)
			printf("%d ", ii1[i] + 1);
		printf("\n");
	}
	return 1;
}

int main() {
	int i;
	long long lower, upper, d2;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	lower = 1, upper = INF;
	while (upper - lower > 1) {
		d2 = (lower + upper) / 2;
		if (solve(d2, 0))
			lower = d2;
		else
			upper = d2;
	}
	solve(lower, 1);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:174:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:176:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65