#include <bits/stdc++.h>
#include "communication.h"
using namespace std;
constexpr int MAXBITS = 30;
constexpr int LEN = 118;
int change_index_extremes_equal(int idx) {
switch (idx) {
case 0: return 0;
case 1: return 0;
case 2: return 1;
case 3: return 2;
case 4: return 1;
case 5: return 2;
case 6: return 3;
case 7: return 3;
}
}
vector<int> change_from_idx_eq(int idx, bool preserve) {
if (preserve) {
switch (idx) {
case 0: return {0, 0, 0, 0};
case 1: return {0, 1, 0, 0};
case 2: return {0, 0, 1, 0};
case 3: return {1, 0, 0, 1};
}
} else {
switch (idx) {
case 0: return {1, 0, 0, 0};
case 1: return {1, 0, 1, 0};
case 2: return {0, 0, 0, 1};
case 3: return {0, 1, 0, 1};
}
}
}
int idx_from_change(int sz, vector<int> ch) {
int cnt = 0;
for (int i = 0; i < (1 << sz); i++) {
bool ok = true;
for (int j = 0; j < sz; j++)
ok &= (i >> j) % 4 != 3;
if (!ok)
continue;
bool match = true;
for (int j = 0; j < sz; j++)
match &= ch[j] == (i >> j) % 2;
if (match)
return cnt;
cnt++;
}
}
vector<int> change_from_idx(int sz, int idx) {
int cnt = 0;
vector<int> ans(sz);
for (int i = 0; i < (1 << sz); i++) {
bool ok = true;
for (int j = 0; j < sz; j++)
ok &= (i >> j) % 4 != 3;
if (!ok)
continue;
if (cnt == idx) {
for (int j = 0; j < sz; j++)
ans[j] = (i >> j) % 2;
return ans;
}
cnt++;
}
}
int send_packet(int sz, vector<int> b) {
vector<int> ch(sz);
for (int i = 0; i < sz; i++) {
ch[i] = b[i] ^ send(b[i]);
}
return idx_from_change(sz, ch);
}
void encode(int N, int X) {
X--;
vector<int> bits(MAXBITS);
for (int i = 0; i < MAXBITS; i++)
bits[i] = (X >> i) & 1;
// Sending message
int last = send_packet(4, {bits[0], bits[1], bits[2], bits[3]});
for (int i = 4; i < MAXBITS; i++) {
last = send_packet(4, {bits[i], (last >> 0) & 1, (last >> 1) & 1, (last >> 2) & 1});
}
// 8 states from 4
last = send_packet(4, {(last >> 0) & 1, (last >> 1) & 1, (last >> 2) & 1, (last >> 0) & 1});
last = change_index_extremes_equal(last);
// 4 states from 3
last = send_packet(2, {(last >> 0) & 1, (last >> 1) & 1});
// Solution for N=3
switch (last) {
case 0: send_packet(4, {0, 0, 0, 0}); break;
case 1: send_packet(4, {0, 1, 1, 0}); break;
case 2: send_packet(4, {1, 0, 0, 1}); break;
}
}
pair<int, int> starting_guesses(vector<int> packet) {
int val = packet[0] | 2 * packet[1] | 4 * packet[2] | 8 * packet[3];
switch (val) {
case 0: return {0, 2};
case 1: return {0, 2};
case 2: return {0, 1};
case 3: return {1, 2};
case 4: return {0, 1};
case 5: return {0, 0};
case 6: return {1, 1};
case 7: return {1, 1};
case 8: return {0, 2};
case 9: return {0, 2};
case 10: return {0, 0};
case 11: return {2, 2};
case 12: return {1, 2};
case 13: return {2, 2};
case 14: return {1, 1};
case 15: return {1, 1};
}
}
int solve(int start, vector<int> packets) {
int changed = start;
auto pop = [&]() {
int ans = packets.back();
packets.pop_back();
return ans;
};
// 3 states to 4
{
vector<int> packet = {pop(), pop()};
vector<int> changes = change_from_idx(2, changed);
reverse(changes.begin(), changes.end());
changed = (changes[0] ^ packet[0]) * 2 | (changes[1] ^ packet[1]);
}
// 4 states to 8
{
vector<int> packet = {pop(), pop(), pop(), pop()};
vector<int> changes = change_from_idx_eq(changed, packet[0] == packet[3]);
reverse(changes.begin(), changes.end());
changed = (changes[1] ^ packet[1]) * 4 | (changes[2] ^ packet[2]) * 2 | (changes[3] ^ packet[3]);
}
// 8 states to full message
int ans = 0;
while (!packets.empty()) {
vector<int> packet = {pop(), pop(), pop(), pop()};
vector<int> changes = change_from_idx(4, changed);
reverse(changes.begin(), changes.end());
if (!packets.empty()) {
changed = (changes[0] ^ packet[0]) * 4 | (changes[1] ^ packet[1]) * 2 | (changes[2] ^ packet[2]);
ans <<= 1;
ans |= changes[3] ^ packet[3];
} else {
for (auto i: {0, 1, 2, 3}) {
ans <<= 1;
ans |= changes[i] ^ packet[i];
}
}
}
return ans;
}
pair<int, int> decode(int N) {
vector<int> packets(LEN);
for (int i = 0; i < LEN; i++)
packets[i] = receive();
vector<int> head(packets.end() - 4, packets.end());
vector<int> tail(packets.begin(), packets.end() - 4);
auto [guess_1, guess_2] = starting_guesses(head);
return {min(N, solve(guess_1, tail) + 1), min(N, solve(guess_2, tail) + 1)};
}
Compilation message
communication.cpp: In function 'int change_index_extremes_equal(int)':
communication.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
19 | }
| ^
communication.cpp: In function 'std::vector<int> change_from_idx_eq(int, bool)':
communication.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
37 | }
| ^
communication.cpp: In function 'int idx_from_change(int, std::vector<int>)':
communication.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
59 | }
| ^
communication.cpp: In function 'std::vector<int> change_from_idx(int, int)':
communication.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
81 | }
| ^
communication.cpp: In function 'std::pair<int, int> starting_guesses(std::vector<int>)':
communication.cpp:138:1: warning: control reaches end of non-void function [-Wreturn-type]
138 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
2708 KB |
Output is correct |
| 2 |
Correct |
131 ms |
2704 KB |
Output is correct |
| 3 |
Correct |
188 ms |
2712 KB |
Output is correct |
| 4 |
Correct |
89 ms |
2712 KB |
Output is correct |
| 5 |
Correct |
129 ms |
2712 KB |
Output is correct |
| 6 |
Correct |
363 ms |
2900 KB |
Output is correct |
| 7 |
Correct |
754 ms |
2712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
877 ms |
2708 KB |
Output is partially correct |
| 2 |
Partially correct |
427 ms |
2708 KB |
Output is partially correct |
| 3 |
Partially correct |
492 ms |
2708 KB |
Output is partially correct |
| 4 |
Partially correct |
861 ms |
2720 KB |
Output is partially correct |
| 5 |
Partially correct |
740 ms |
2720 KB |
Output is partially correct |
| 6 |
Partially correct |
633 ms |
2912 KB |
Output is partially correct |
| 7 |
Partially correct |
2552 ms |
2796 KB |
Output is partially correct |
| 8 |
Partially correct |
3928 ms |
2960 KB |
Output is partially correct |
| 9 |
Partially correct |
3499 ms |
2872 KB |
Output is partially correct |
| 10 |
Partially correct |
3509 ms |
2884 KB |
Output is partially correct |
| 11 |
Partially correct |
3395 ms |
2876 KB |
Output is partially correct |
| 12 |
Partially correct |
3483 ms |
2872 KB |
Output is partially correct |
| 13 |
Partially correct |
3446 ms |
3076 KB |
Output is partially correct |
| 14 |
Partially correct |
3494 ms |
2956 KB |
Output is partially correct |
| 15 |
Partially correct |
1827 ms |
2972 KB |
Output is partially correct |
| 16 |
Partially correct |
3773 ms |
2788 KB |
Output is partially correct |
| 17 |
Partially correct |
936 ms |
3052 KB |
Output is partially correct |
| 18 |
Partially correct |
934 ms |
2880 KB |
Output is partially correct |
| 19 |
Partially correct |
866 ms |
2788 KB |
Output is partially correct |
| 20 |
Partially correct |
912 ms |
2892 KB |
Output is partially correct |
| 21 |
Partially correct |
929 ms |
2892 KB |
Output is partially correct |
| 22 |
Partially correct |
958 ms |
3040 KB |
Output is partially correct |
| 23 |
Partially correct |
1530 ms |
2872 KB |
Output is partially correct |
| 24 |
Correct |
89 ms |
2716 KB |
Output is correct |
| 25 |
Correct |
135 ms |
2896 KB |
Output is correct |
| 26 |
Correct |
178 ms |
2704 KB |
Output is correct |
| 27 |
Correct |
82 ms |
2900 KB |
Output is correct |
| 28 |
Correct |
129 ms |
2716 KB |
Output is correct |
| 29 |
Correct |
349 ms |
2796 KB |
Output is correct |
| 30 |
Correct |
774 ms |
2708 KB |
Output is correct |
