Submission #592856

#	Time	Username	Problem	Language	Result	Execution time	Memory
592856		rainboy	Flight to the Ford (BOI22_communication)	C++17	100 / 100	2945 ms	1956 KiB

communication

#if 1
#include "communication.h"
#include <string.h>

using namespace std;

typedef pair<int, int> pi;

const int N = 400;

void split(int *ll, int *rr, int n, int ll_[][N], int rr_[][N], int *nn_, int s) {
	int i;

	if (s == 0) {
		nn_[0] = 0;
		nn_[1] = n;
		memcpy(ll_[1], ll, nn_[1] * sizeof *ll);
		memcpy(rr_[1], rr, nn_[1] * sizeof *rr);
		return;
	}
	for (i = 0; i < n; i++) {
		s -= rr[i] - ll[i] + 1;
		if (s == 0) {
			nn_[0] = i + 1;
			memcpy(ll_[0], ll, nn_[0] * sizeof *ll);
			memcpy(rr_[0], rr, nn_[0] * sizeof *rr);
			if ((nn_[1] = n - 1 - i) > 0) {
				memcpy(ll_[1], ll + i + 1, nn_[1] * sizeof *ll);
				memcpy(rr_[1], rr + i + 1, nn_[1] * sizeof *rr);
			}
			return;
		} else if (s < 0) {
			nn_[0] = i + 1;
			memcpy(ll_[0], ll, nn_[0] * sizeof *ll);
			memcpy(rr_[0], rr, nn_[0] * sizeof *rr), rr_[0][i] = rr[i] + s;
			nn_[1] = n - i;
			memcpy(ll_[1], ll + i, nn_[1] * sizeof *ll), ll_[1][0] = rr[i] + s + 1;
			memcpy(rr_[1], rr + i, nn_[1] * sizeof *rr);
			return;
		}
	}
}

int merge(int *ll0, int *rr0, int n0, int *ll1, int *rr1, int n1, int *ll, int *rr) {
	int i = 0, j = 0, k = 0;

	while (i < n0 && j < n1)
		if (ll0[i] < ll1[j])
			ll[k] = ll0[i], rr[k] = rr0[i], i++, k++;
		else
			ll[k] = ll1[j], rr[k] = rr1[j], j++, k++;
	while (i < n0)
		ll[k] = ll0[i], rr[k] = rr0[i], i++, k++;
	while (j < n1)
		ll[k] = ll1[j], rr[k] = rr1[j], j++, k++;
	return n0 + n1;
}

int contains(int *ll, int *rr, int n, int a) {
	int i;

	for (i = 0; i < n; i++)
		if (ll[i] <= a && a <= rr[i])
			return 1;
	return 0;
}

void encode(int s, int a) {
	int ll[2][N], rr[2][N], nn[2], ll_[2][2][N], rr_[2][2][N], nn_[2][2], ss[2], h, i, b;

	nn[0] = nn[1] = 0;
	ll[0][nn[0]] = 1, rr[0][nn[0]] = s, nn[0]++;
	while (1) {
		for (h = 0; h < 2; h++) {
			ss[h] = 0;
			for (i = 0; i < nn[h]; i++)
				ss[h] += rr[h][i] - ll[h][i] + 1;
		}
		if (ss[0] + ss[1] <= 2)
			return;
		if (ss[0] == 2 && ss[1] == 1) {
			int x = ll[0][0], y = rr[0][nn[0] - 1], z = ll[1][0];

			if (send(a == x || a == y ? 0 : 1) == 1)
				send(a == x || a == z ? 0 : 1);
			return;
		}
		ss[0] /= 2, ss[1] = (ss[1] + 1) / 2;
		for (h = 0; h < 2; h++)
			split(ll[h], rr[h], nn[h], ll_[h], rr_[h], nn_[h], ss[h]);
		for (h = 0; h < 2; h++)
			for (b = 0; b < 2; b++)
				if (contains(ll_[h][b], rr_[h][b], nn_[h][b], a))
					goto out;
out:
		b = send(b);
		nn[0] = merge(ll_[0][b], rr_[0][b], nn_[0][b], ll_[1][b], rr_[1][b], nn_[1][b], ll[0], rr[0]);
		nn[1] = nn_[0][b ^ 1];
		memcpy(ll[1], ll_[0][b ^ 1], nn[1] * sizeof *ll_[0][b ^ 1]);
		memcpy(rr[1], rr_[0][b ^ 1], nn[1] * sizeof *rr_[0][b ^ 1]);
	}
}

pi decode(int s) {
	int ll[2][N], rr[2][N], nn[2], ll_[2][2][N], rr_[2][2][N], nn_[2][2], ss[2], h, i, b;

	nn[0] = nn[1] = 0;
	ll[0][nn[0]] = 1, rr[0][nn[0]] = s, nn[0]++;
	while (1) {
		for (h = 0; h < 2; h++) {
			ss[h] = 0;
			for (i = 0; i < nn[h]; i++)
				ss[h] += rr[h][i] - ll[h][i] + 1;
		}
		if (ss[0] + ss[1] <= 2) {
			if (ss[1] == 0)
				return make_pair(ll[0][0], rr[0][nn[0] - 1]);
			else if (ss[0] == 0)
				return make_pair(ll[1][0], rr[1][nn[1] - 1]);
			else
				return make_pair(ll[0][0], ll[1][0]);
		}
		if (ss[0] == 2 && ss[1] == 1) {
			int x = ll[0][0], y = rr[0][nn[0] - 1], z = ll[1][0];

			return receive() == 0 ? make_pair(x, y) : make_pair(receive() == 0 ? x : y, z);
		}
		ss[0] /= 2, ss[1] = (ss[1] + 1) / 2;
		for (h = 0; h < 2; h++)
			split(ll[h], rr[h], nn[h], ll_[h], rr_[h], nn_[h], ss[h]);
		b = receive();
		nn[0] = merge(ll_[0][b], rr_[0][b], nn_[0][b], ll_[1][b], rr_[1][b], nn_[1][b], ll[0], rr[0]);
		nn[1] = nn_[0][b ^ 1];
		memcpy(ll[1], ll_[0][b ^ 1], nn[1] * sizeof *ll_[0][b ^ 1]);
		memcpy(rr[1], rr_[0][b ^ 1], nn[1] * sizeof *rr_[0][b ^ 1]);
	}
}
#else
#include <stdio.h>

#define S	1000000000

int main() {
	int s, a, b, c, tmp;

	s = S, a = s, b = 0, c = 0;
	while (a + b > 3) {
		printf("%d %d %d\n", a, b, ++c);
		if (a % 2 == 0 && b % 2 == 0)
			tmp = (a + b) / 2, b = a / 2, a = tmp;
		else if (a % 2 == 0 && b % 2 != 0)
			tmp = (a + b) / 2 + 1, b = a / 2, a = tmp;
		else if (a % 2 != 0 && b % 2 == 0)
			tmp = (a + b) / 2 + 1, b = a / 2, a = tmp;
		else
			tmp = (a + b) / 2, b = a / 2 + 1, a = tmp;
	}
	return 0;
}
#endif

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85