#include "communication.h"
#include <bits/stdc++.h>
using namespace std;
//
// --- Sample implementation for the task communication ---
//
// To compile this program with the sample grader, place:
// communication.h communication_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
// g++ -std=c++17 communication_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//
bool split(set<array<int, 2>>& s, int p) {
if (p == INT_MIN) return false;
auto it = s.lower_bound({p, p - 1}); // Use p-1 to handle array<int, >= 2> case.
if (it == s.begin()) return false;
--it;
auto cur = *it;
assert(cur[0] < p);
if (cur[1] < p) return false;
s.erase(it);
auto l = cur;
l[1] = p - 1;
s.insert(l); // {cur[0], p - 1, cur[2...]}
auto r = cur;
r[0] = p;
s.insert(r); // {p, cur[1], cur[2...]}
return true;
}
template <typename F>
pair<int, int> protocol(int n, F&& getBitReceived) {
const int SMALL = 50;
const int INF = 1e9;
vector<vector<int>> dp(SMALL, vector<int>(SMALL, INF));
vector<vector<array<int, 2>>> move(SMALL, vector<array<int, 2>>(SMALL));
for (int s = 0; s < SMALL; ++s)
for (int a = 0; a <= s; ++a) {
int b = s - a;
if (s <= 2) {
dp[a][b] = 0;
continue;
}
for (int a0 = 0; a0 <= a; ++a0)
for (int b0 = 0; b0 <= b; ++b0) {
if (a != a0 && b != b0) assert(dp[a0][b0] <= dp[a][b]);
// Note we ignore a' + b' == a + b and a' >= a to prevent cycles,
// but that's OK since it is not needed to consider those. (no proof, so dp[a][b] may not be optimal)
int v = max(dp[a0 + b0][a - a0], dp[s - a0 - b0][a0]) + 1;
if (v < dp[a][b]) {
dp[a][b] = v;
move[a][b] = {a0, b0};
}
}
assert(dp[a][b] < INF);
}
set<array<int, 2>> lastTrue, lastFalse;
lastTrue.insert({1, n});
int a = n, b = 0;
while (a + b > 2) {
int a0 = a / 2, b0 = b / 2;
if (a + b < move.size()) {
a0 = move[a][b][0];
b0 = move[a][b][1];
}
auto findKthPoint = [&](const set<array<int, 2>>& s, int k) {
for (auto& i : s) {
if (i[1] - i[0] + 1 >= k) {
return i[0] + k - 1;
}
k -= i[1] - i[0] + 1;
}
return 0;
};
int p0 = findKthPoint(lastTrue, a0);
split(lastTrue, p0 + 1);
set<array<int, 2>> T0, T1, F0, F1;
for (auto& i : lastTrue)
if (i[1] <= p0) T0.insert(i);
else T1.insert(i);
int q0 = findKthPoint(lastFalse, b0);
split(lastFalse, q0 + 1);
for (auto& i : lastFalse)
if (i[1] <= q0) F0.insert(i);
else F1.insert(i);
auto S = T0;
S.insert(F0.begin(), F0.end());
int bit = getBitReceived(S);
if (bit == 1) {
lastTrue = S;
lastFalse = T1;
} else {
lastTrue = T1;
lastTrue.insert(F1.begin(), F1.end());
lastFalse = T0;
}
a = b = 0;
for (auto& i : lastTrue) a += i[1] - i[0] + 1;
for (auto& i : lastFalse) b += i[1] - i[0] + 1;
}
auto S = lastTrue;
S.insert(lastFalse.begin(), lastFalse.end());
pair<int, int> ret = {-1, -1};
for (auto& i : S) {
if (ret.first == -1) ret.first = ret.second = i[0];
else ret.second = i[0];
if (i[1] > i[0]) ret.second = i[1];
}
return ret;
}
void encode(int N, int X) {
protocol(N, [&](const set<array<int, 2>>& S) {
// Returns bit that is received.
int bit = 0;
for (auto& i : S) if (i[0] <= X && X <= i[1]) bit = 1;
return send(bit);
});
}
pair<int, int> decode(int N) {
auto possibles = protocol(N, [&](const set<array<int, 2>>& S) {
// Returns bit that is received.
return receive();
});
return possibles;
}
Compilation message
communication.cpp: In instantiation of 'std::pair<int, int> protocol(int, F&&) [with F = encode(int, int)::<lambda(const std::set<std::array<int, 2> >&)>]':
communication.cpp:121:3: required from here
communication.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if (a + b < move.size()) {
| ~~~~~~^~~~~~~~~~~~~
communication.cpp: In instantiation of 'std::pair<int, int> protocol(int, F&&) [with F = decode(int)::<lambda(const std::set<std::array<int, 2> >&)>]':
communication.cpp:128:3: required from here
communication.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 2> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
1888 KB |
Output is correct |
| 2 |
Correct |
104 ms |
1832 KB |
Output is correct |
| 3 |
Correct |
136 ms |
1800 KB |
Output is correct |
| 4 |
Correct |
74 ms |
1792 KB |
Output is correct |
| 5 |
Correct |
105 ms |
1824 KB |
Output is correct |
| 6 |
Correct |
319 ms |
1968 KB |
Output is correct |
| 7 |
Correct |
508 ms |
1800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1288 ms |
1832 KB |
Output is correct |
| 2 |
Correct |
627 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
822 ms |
1784 KB |
Output is correct |
| 4 |
Correct |
1469 ms |
1852 KB |
Output is correct |
| 5 |
Correct |
1235 ms |
1976 KB |
Output is correct |
| 6 |
Correct |
1037 ms |
1860 KB |
Output is correct |
| 7 |
Correct |
3969 ms |
1992 KB |
Output is correct |
| 8 |
Correct |
6965 ms |
2388 KB |
Output is correct |
| 9 |
Correct |
5537 ms |
2220 KB |
Output is correct |
| 10 |
Correct |
5781 ms |
2100 KB |
Output is correct |
| 11 |
Correct |
6076 ms |
2348 KB |
Output is correct |
| 12 |
Correct |
5652 ms |
2308 KB |
Output is correct |
| 13 |
Correct |
5739 ms |
2308 KB |
Output is correct |
| 14 |
Correct |
5778 ms |
2200 KB |
Output is correct |
| 15 |
Correct |
2772 ms |
2068 KB |
Output is correct |
| 16 |
Correct |
6370 ms |
2116 KB |
Output is correct |
| 17 |
Correct |
1476 ms |
1984 KB |
Output is correct |
| 18 |
Correct |
1496 ms |
2084 KB |
Output is correct |
| 19 |
Correct |
1533 ms |
2072 KB |
Output is correct |
| 20 |
Correct |
1550 ms |
2036 KB |
Output is correct |
| 21 |
Correct |
1613 ms |
1964 KB |
Output is correct |
| 22 |
Correct |
1609 ms |
1856 KB |
Output is correct |
| 23 |
Correct |
2494 ms |
2132 KB |
Output is correct |
| 24 |
Correct |
76 ms |
1820 KB |
Output is correct |
| 25 |
Correct |
105 ms |
1852 KB |
Output is correct |
| 26 |
Correct |
142 ms |
1824 KB |
Output is correct |
| 27 |
Correct |
72 ms |
1848 KB |
Output is correct |
| 28 |
Correct |
105 ms |
1788 KB |
Output is correct |
| 29 |
Correct |
276 ms |
1956 KB |
Output is correct |
| 30 |
Correct |
523 ms |
1740 KB |
Output is correct |
