#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
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
