oj.uz

답안 #592856

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
592856 2022-07-09T16:55:48 Z rainboy Flight to the Ford (BOI22_communication) C++17
100 / 100
 2945 ms 1956 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1772 KB Output is correct
2 Correct 6 ms 1688 KB Output is correct
3 Correct 5 ms 1724 KB Output is correct
4 Correct 7 ms 1680 KB Output is correct
5 Correct 8 ms 1724 KB Output is correct
6 Correct 18 ms 1868 KB Output is correct
7 Correct 30 ms 1768 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 585 ms 1788 KB Output is correct
2 Correct 363 ms 1668 KB Output is correct
3 Correct 396 ms 1704 KB Output is correct
4 Correct 634 ms 1732 KB Output is correct
5 Correct 658 ms 1700 KB Output is correct
6 Correct 522 ms 1692 KB Output is correct
7 Correct 1778 ms 1784 KB Output is correct
8 Correct 2681 ms 1904 KB Output is correct
9 Correct 2415 ms 1876 KB Output is correct
10 Correct 2695 ms 1952 KB Output is correct
11 Correct 2269 ms 1908 KB Output is correct
12 Correct 2518 ms 1784 KB Output is correct
13 Correct 2359 ms 1920 KB Output is correct
14 Correct 2549 ms 1916 KB Output is correct
15 Correct 1218 ms 1844 KB Output is correct
16 Correct 2945 ms 1744 KB Output is correct
17 Correct 666 ms 1804 KB Output is correct
18 Correct 719 ms 1860 KB Output is correct
19 Correct 661 ms 1848 KB Output is correct
20 Correct 590 ms 1788 KB Output is correct
21 Correct 729 ms 1688 KB Output is correct
22 Correct 892 ms 1848 KB Output is correct
23 Correct 1218 ms 1776 KB Output is correct
24 Correct 7 ms 1700 KB Output is correct
25 Correct 8 ms 1800 KB Output is correct
26 Correct 10 ms 1760 KB Output is correct
27 Correct 5 ms 1740 KB Output is correct
28 Correct 10 ms 1704 KB Output is correct
29 Correct 19 ms 1956 KB Output is correct
30 Correct 35 ms 1644 KB Output is correct