#include"communication.h"
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
// <|°_°|>
// M. Broccoli
const int LOG = 30;
pair <int, int> Dsu[LOG];
int Fixed[LOG];
int Ans[LOG];
int Find(int a) {
return Dsu[a].first < 0 ? a : Find(Dsu[a].first);
}
int Path(int a) {
return Dsu[a].first < 0 ? 0 : Dsu[a].second ^ Path(Dsu[a].first);
}
void Union(int a, int b, int link) {
a = Find(a), b = Find(b);
if (a == b)
return;
Dsu[a] = {b, link};
return;
}
pair <int, int> DecodeStep(vector <int> &Bits) {
vector <int> Poss(4);
Poss[0] = Poss[1] = 1;
Poss[2] = Poss[3] = 0;
for (int i = 0; i < 4; i ++)
{
if (i && Bits[i] == Bits[i - 1])
{
Poss[Bits[i] ^ 1] --;
if (i == 2)
{
Poss[2 ^ Bits[i]] ++;
Poss[3 ^ Bits[i]] -= 42;
}
else
Poss[3 ^ Bits[i]] ++;
}
}
vector <int> ans;
for (int i = 0; i < 4; i ++)
{
if (Poss[i] > 0)
ans.push_back(i);
}
if (ans.size() == 1)
return {ans[0], ans[0]};
return {ans[0], ans[1]};
}
pair <int, int> EncodeStep(int a) {
vector <int> ToSend(4, 0);
if (a == 0)
ToSend = {0, 0, 0, 0};
if (a == 1)
ToSend = {1, 1, 1, 1};
if (a == 2)
ToSend = {1, 0, 0, 1};
if (a == 3)
ToSend = {0, 1, 1, 0};
for (int i = 0; i < 4; i ++)
{
ToSend[i] = send(ToSend[i]);
}
return DecodeStep(ToSend);
}
int Log(int n) {
return n == 1 ? 0 : 1 + Log(n / 2);
}
void encode(int nbMessages, int message) {
message --;
fill_n(Fixed, LOG, 0);
fill_n(Dsu, LOG, make_pair(-1, 0));
int last = 0;
for (int i = 1; (1 << i) < nbMessages; i ++)
{
int cur = (message >> i) & 1;
int bit = (message >> last) & 1;
pair <int, int> x = EncodeStep(2 * cur + bit);
if ((x.first & 1) == (x.second & 1))
Fixed[Find(last)] = 1;
if ((x.first & 2) == (x.second & 2))
Fixed[Find(i)] = 1;
if ((x.first ^ x.second) == 3)
Union(i, last, 0);
while (Fixed[Find(last)] == 1 && last < i)
last ++;
}
return;
}
pair <int, int> decode(int nbMessages) {
fill_n(Fixed, LOG, 0);
fill_n(Dsu, LOG, make_pair(-1, 0));
fill_n(Ans, LOG, -1);
vector <int> Read(4, 0);
int last = 0;
for (int i = 1; (1 << i) < nbMessages; i ++)
{
for (int j = 0; j < 4; j ++)
{
Read[j] = receive();
}
pair <int, int> x = DecodeStep(Read);
if ((x.first & 1) == (x.second & 1))
{
Fixed[Find(last)] = 1;
Ans[last] = x.first & 1;
}
if ((x.first & 2) == (x.second & 2))
{
Fixed[Find(i)] = 1;
Ans[i] = (x.first >> 1) & 1;
}
if ((x.first ^ x.second) == 3)
Union(i, last, (x.first & 1) ^ (x.first & 2));
while (Fixed[Find(last)] == 1 && last < i)
last ++;
}
for (int i = 0; (1 << i) < nbMessages; i ++)
{
if (Ans[i] >= 0)
Ans[Find(i)] = Path(i) ^ Ans[i];
}
int both = -1;
for (int i = 0; (1 << i) < nbMessages; i ++)
{
if (Ans[Find(i)] < 0)
both = Find(i);
}
pair <int, int> ans = {1, 1};
if (both >= 0)
Ans[both] = 0;
for (int i = 0; (1 << i) < nbMessages; i ++)
{
Ans[i] = Path(i) ^ Ans[Find(i)];
}
for (int i = 0; (1 << i) < nbMessages; i ++)
{
ans.first += Ans[i] << i;
}
Ans[both] = 1;
for (int i = 0; (1 << i) < nbMessages; i ++)
{
Ans[i] = Path(i) ^ Ans[Find(i)];
}
for (int i = 0; (1 << i) < nbMessages; i ++)
{
ans.second += Ans[i] << i;
}
ans.first = min(ans.first, nbMessages);
ans.second = min(ans.second, nbMessages);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1748 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1744 KB |
Output is correct |
| 3 |
Correct |
21 ms |
1780 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1736 KB |
Output is correct |
| 5 |
Correct |
15 ms |
1684 KB |
Output is correct |
| 6 |
Correct |
36 ms |
1828 KB |
Output is correct |
| 7 |
Correct |
48 ms |
1664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
965 ms |
1676 KB |
Output is partially correct |
| 2 |
Partially correct |
346 ms |
1728 KB |
Output is partially correct |
| 3 |
Partially correct |
545 ms |
1672 KB |
Output is partially correct |
| 4 |
Partially correct |
938 ms |
1736 KB |
Output is partially correct |
| 5 |
Partially correct |
699 ms |
1672 KB |
Output is partially correct |
| 6 |
Partially correct |
507 ms |
1684 KB |
Output is partially correct |
| 7 |
Partially correct |
2433 ms |
1792 KB |
Output is partially correct |
| 8 |
Partially correct |
3407 ms |
2032 KB |
Output is partially correct |
| 9 |
Partially correct |
3114 ms |
1792 KB |
Output is partially correct |
| 10 |
Partially correct |
3122 ms |
1912 KB |
Output is partially correct |
| 11 |
Partially correct |
3036 ms |
1952 KB |
Output is partially correct |
| 12 |
Partially correct |
3011 ms |
1880 KB |
Output is partially correct |
| 13 |
Partially correct |
3015 ms |
1936 KB |
Output is partially correct |
| 14 |
Partially correct |
3093 ms |
1800 KB |
Output is partially correct |
| 15 |
Partially correct |
1741 ms |
1784 KB |
Output is partially correct |
| 16 |
Partially correct |
3801 ms |
1720 KB |
Output is partially correct |
| 17 |
Partially correct |
689 ms |
1804 KB |
Output is partially correct |
| 18 |
Partially correct |
866 ms |
1800 KB |
Output is partially correct |
| 19 |
Partially correct |
851 ms |
1756 KB |
Output is partially correct |
| 20 |
Partially correct |
795 ms |
1720 KB |
Output is partially correct |
| 21 |
Partially correct |
975 ms |
1860 KB |
Output is partially correct |
| 22 |
Partially correct |
840 ms |
1776 KB |
Output is partially correct |
| 23 |
Partially correct |
1483 ms |
1744 KB |
Output is partially correct |
| 24 |
Correct |
10 ms |
1816 KB |
Output is correct |
| 25 |
Correct |
12 ms |
1720 KB |
Output is correct |
| 26 |
Correct |
20 ms |
1716 KB |
Output is correct |
| 27 |
Correct |
13 ms |
1684 KB |
Output is correct |
| 28 |
Correct |
13 ms |
1792 KB |
Output is correct |
| 29 |
Correct |
25 ms |
1764 KB |
Output is correct |
| 30 |
Correct |
42 ms |
1752 KB |
Output is correct |
