#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int prob = 1;
#include "communication.h"
int dec3(int x)//4 bit x
{
vector<int>ger;
for (int m = 0; m < 16; m++)
{
bool ok = true;
int v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
int V[4] = {0, 0, 6, 9};
for (int i = 1; i <= 3; i++)
{
bool ok = true;
for (int j : ger)
if (x == (V[i] ^ j))
ok = false;
if (ok)
return i;
}
assert(false);
return 0;
}
int enc3(int X)
{
int v = 0;
if (X == 1)
v = 0;
else if (X == 2)
v = 6;
else if (X == 3)
v = 9;
int val = 0;
for (int t = 0; t < 4; t++)
{
val += send(v % 2) << t;
v /= 2;
}
return dec3(val);
}
string S4[4] = {"1000",
"0001",
"1110",
"0111"
};
string S6[6] = {"00000",
"00001",
"00110",
"01111",
"10010",
"11111"
};
string S8[8] = {"000000",
"000010",
"011001",
"011011",
"100100",
"100110",
"111101",
"111111",
};
string S10[10] = {"000010",
"111101",
"000011",
"111100",
"000100",
"111011",
"000101",
"111010",
"000110",
"111001",
};
int conv4(int i)
{
int v = 0;
int p = 1;
for (char c : S4[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
int conv6(int i)
{
int v = 0;
int p = 1;
for (char c : S6[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
int conv8(int i)
{
int v = 0;
int p = 1;
for (char c : S8[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
int conv10(int i)
{
int v = 0;
int p = 1;
for (char c : S10[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
bitset<8> dec8(int x)//6 bit x
{
vector<int>ger;
for (int m = 0; m < 64; m++)
{
bool ok = true;
int v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
bitset<8>ret;
for (int i = 0; i < 8; i++)
{
for (int j : ger)
if (x == (conv8(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<10> dec10(int x)//6 bit x
{
vector<int>ger;
for (int m = 0; m < 64; m++)
{
bool ok = true;
int v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
bitset<10>ret;
for (int i = 0; i < 10; i++)
{
for (int j : ger)
if (x == (conv10(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<6> dec6(int x)//5 bit x
{
vector<int>ger;
for (int m = 0; m < 32; m++)
{
bool ok = true;
int v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
bitset<6>ret;
for (int i = 0; i < 6; i++)
{
for (int j : ger)
if (x == (conv6(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<4> dec4(int x)//4 bit x
{
vector<int>ger;
for (int m = 0; m < 16; m++)
{
bool ok = true;
int v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
bitset<4>ret;
for (int i = 0; i < 4; i++)
{
for (int j : ger)
if (x == (conv4(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<4> enc4(int X)
{
int v = conv4(X);
int val = 0;
for (int t = 0; t < 4; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec4(val);
assert(ret[X] == true);
return ret;
}
bitset<10> enc10(int X)
{
int v = conv10(X);
int val = 0;
for (int t = 0; t < 6; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec10(val);
assert(ret[X] == true);
return ret;
}
bitset<8> enc8(int X)
{
int v = conv8(X);
int val = 0;
for (int t = 0; t < 6; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec8(val);
assert(ret[X] == true);
return ret;
}
bitset<6> enc6(int X)
{
int v = conv6(X);
int val = 0;
for (int t = 0; t < 5; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec6(val);
assert(ret[X] == true);
return ret;
}
void encode(int N, int X)
{
if (N < 3)
return;
if (N == 3)
{
enc3(X);
return;
}
if (N >= 10)
{
int v = N / 10;
int vv = (X - 1) / v;
vv = min(vv, 9);
bitset<10>gal = enc10(vv);
int sz[10] = {v, v, v, v, v, v, v, v, v, N - 9 * v};
int s = 0;
for (int i = 0; i < 10; i++)
{
if (gal[i])
{
s += sz[i];
}
else if (i < vv)
X -= sz[i];
}
encode(s, X);
return;
}
if (N >= 4)
{
int v = N / 4;
int vv = (X - 1) / v;
vv = min(vv, 3);
bitset<4>gal = enc4(vv);
int sz[4] = {v, v, v, N - 3 * v};
int s = 0;
for (int i = 0; i < 4; i++)
{
if (gal[i])
{
s += sz[i];
}
else if (i < vv)
X -= sz[i];
}
encode(s, X);
return;
}
if (N >= 8)
{
int v = N / 8;
int vv = (X - 1) / v;
vv = min(vv, 7);
bitset<8>gal = enc8(vv);
int sz[8] = {v, v, v, v, v, v, v, N - 7 * v};
int s = 0;
for (int i = 0; i < 8; i++)
{
if (gal[i])
{
s += sz[i];
}
else if (i < vv)
X -= sz[i];
}
encode(s, X);
return;
}
if (N >= 6)
{
int v = N / 6;
int vv = (X - 1) / v;
vv = min(vv, 5);
bitset<6>gal = enc6(vv);
int sz[6] = {v, v, v, v, v, N - 5 * v};
int s = 0;
for (int i = 0; i < 6; i++)
{
if (gal[i])
{
s += sz[i];
}
else if (i < vv)
X -= sz[i];
}
encode(s, X);
return;
}
int v = N / 3;
int vv = 3;
if (X <= v)
vv = 1;
else if (X <= 2 * v)
vv = 2;
int val = enc3(vv);
assert(val != vv);
if (val == 2)
{
if (vv == 1)
encode(N - v, X);
if (vv == 3)
encode(N - v, X - v);
}
if (val == 1)
encode(N - v, X - v);
if (val == 3)
encode(2 * v, X);
}
pair<int, int> decode(int N)
{
if (N == 1)
return {1, 1};
if (N == 2)
return {1, 2};
if (N == 3)
{
int val = 0;
for (int t = 0; t < 4; t++)
val += receive() << t;
int v = dec3(val);
pair<int, int>ans = {1, 2};
if (v == 1)
ans.first = 3;
if (v == 2)
ans.second = 3;
return ans;
}
else if (N >= 10)
{
int re = 0;
for (int t = 0; t < 6; t++)
re += receive() << t;
bitset<10> gal = dec10(re);
int v = N / 10;
int sz[10] = {v, v, v, v, v, v, v, v, v, N - 9 * v};
int s = 0;
for (int i = 0; i < 10; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s);
int sum = 0;
bool ger1 = false;
bool ger2 = false;
for (int i = 0; i < 10; i++)
{
if (gal[i])
{
if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.first += sz[j];
ger1 = true;
}
if (r.second > sum && r.second <= sum + sz[i] && ger2 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.second += sz[j];
ger2 = true;
}
sum += sz[i];
}
}
return r;
}
else if (N >= 4)
{
int re = 0;
for (int t = 0; t < 4; t++)
re += receive() << t;
bitset<4> gal = dec4(re);
int v = N / 4;
int sz[4] = {v, v, v, N - 3 * v};
int s = 0;
for (int i = 0; i < 4; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s);
int sum = 0;
bool ger1 = false;
bool ger2 = false;
for (int i = 0; i < 4; i++)
{
if (gal[i])
{
if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.first += sz[j];
ger1 = true;
}
if (r.second > sum && r.second <= sum + sz[i] && ger2 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.second += sz[j];
ger2 = true;
}
sum += sz[i];
}
}
return r;
}
else if (N >= 8)
{
int re = 0;
for (int t = 0; t < 6; t++)
re += receive() << t;
bitset<8> gal = dec8(re);
int v = N / 8;
int sz[8] = {v, v, v, v, v, v, v, N - 7 * v};
int s = 0;
for (int i = 0; i < 8; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s);
int sum = 0;
bool ger1 = false;
bool ger2 = false;
for (int i = 0; i < 8; i++)
{
if (gal[i])
{
if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.first += sz[j];
ger1 = true;
}
if (r.second > sum && r.second <= sum + sz[i] && ger2 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.second += sz[j];
ger2 = true;
}
sum += sz[i];
}
}
return r;
}
else if (N >= 6)
{
int re = 0;
for (int t = 0; t < 5; t++)
re += receive() << t;
bitset<6> gal = dec6(re);
int v = N / 6;
int sz[6] = {v, v, v, v, v, N - 5 * v};
int s = 0;
for (int i = 0; i < 6; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s);
int sum = 0;
bool ger1 = false;
bool ger2 = false;
for (int i = 0; i < 6; i++)
{
if (gal[i])
{
if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.first += sz[j];
ger1 = true;
}
if (r.second > sum && r.second <= sum + sz[i] && ger2 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.second += sz[j];
ger2 = true;
}
sum += sz[i];
}
}
return r;
}
else
{
int re = 0;
for (int t = 0; t < 4; t++)
re += receive() << t;
int val = dec3(re);
int v = N / 3;
if (val == 2)
{
pair<int, int>r = decode(N - v);
if (r.first > v)
r.first += v;
if (r.second > v)
r.second += v;
return r;
}
if (val == 1)
{
pair<int, int>r = decode(N - v);
r.first += v;
r.second += v;
return r;
}
if (val == 3)
return decode(2 * v);
}
return { -1, -1};
}
const int bitcnt = 4;
const int bitsz = 1 << bitcnt;
const int cnt2 = 4;
// int main()
// {
// // vector<int>ger;
// // for (int m = 0; m < bitsz; m++)
// // {
// // bool ok = true;
// // int v = m;
// // while (v != 0)
// // {
// // if (v % 4 == 3)
// // ok = false;
// // v /= 2;
// // }
// // if (ok)
// // ger.push_back(m);
// // }
// // bitset<bitsz>gal[bitsz];
// // for (int m = 0; m < bitsz; m++)
// // for (int v : ger)
// // gal[m][m ^ v] = true;
// // int v[100];
// // v[0] = 0;
// // int rec = 5000;
// // mt19937_64 rng(0);
// // for (int tst = 0; tst < 10000000; tst++) {
// // for (int i = 0; i < cnt2 / 2; i++)
// // v[i] = rng() % bitsz;
// // for (int i = cnt2 - 1; i >= cnt2 / 2; i--)
// // v[i] = v[cnt2 - 1 - i] ^ (bitsz - 1);
// // int mx = 0;
// // for (int i = 0; i < cnt2; i++)
// // {
// // for (int m : ger)
// // {
// // int cnt = 0;
// // int rec = v[i] ^ m;
// // for (int t = 0; t < cnt2; t++)
// // if (gal[v[t]][rec])
// // cnt++;
// // mx = max(mx, cnt);
// // }
// // if (mx >= rec)
// // break;
// // }
// // if (mx < rec)
// // {
// // cout << mx << endl;
// // for (int t = 0; t < cnt2; t++)
// // cout << bitset<bitcnt>(v[t]) << endl;
// // cout << endl;
// // rec = mx;
// // }
// // }
// // return 0;
// for (int t = 0; t < 1000; t++)
// {
// int N = 10;
// int val = (t % N) + 1;
// encode(N, val);
// pair<int, int>v = decode(N);
// cout << v.first << " " << v.second << endl;
// assert(v.first == val || v.second == val);
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1688 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1784 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1688 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1756 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1692 KB |
Output is correct |
| 6 |
Correct |
28 ms |
1744 KB |
Output is correct |
| 7 |
Correct |
36 ms |
1732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
957 ms |
1716 KB |
Output is partially correct |
| 2 |
Partially correct |
511 ms |
1800 KB |
Output is partially correct |
| 3 |
Partially correct |
626 ms |
1664 KB |
Output is partially correct |
| 4 |
Partially correct |
1083 ms |
1824 KB |
Output is partially correct |
| 5 |
Partially correct |
912 ms |
1740 KB |
Output is partially correct |
| 6 |
Partially correct |
735 ms |
1676 KB |
Output is partially correct |
| 7 |
Partially correct |
3058 ms |
1836 KB |
Output is partially correct |
| 8 |
Partially correct |
4171 ms |
1972 KB |
Output is partially correct |
| 9 |
Partially correct |
3792 ms |
1876 KB |
Output is partially correct |
| 10 |
Partially correct |
3768 ms |
2008 KB |
Output is partially correct |
| 11 |
Partially correct |
3924 ms |
1956 KB |
Output is partially correct |
| 12 |
Partially correct |
4010 ms |
1788 KB |
Output is partially correct |
| 13 |
Partially correct |
4596 ms |
1812 KB |
Output is partially correct |
| 14 |
Partially correct |
4122 ms |
1896 KB |
Output is partially correct |
| 15 |
Partially correct |
2059 ms |
1808 KB |
Output is partially correct |
| 16 |
Partially correct |
4142 ms |
1836 KB |
Output is partially correct |
| 17 |
Partially correct |
1242 ms |
1816 KB |
Output is partially correct |
| 18 |
Partially correct |
1089 ms |
1872 KB |
Output is partially correct |
| 19 |
Partially correct |
1186 ms |
1732 KB |
Output is partially correct |
| 20 |
Partially correct |
1165 ms |
1892 KB |
Output is partially correct |
| 21 |
Partially correct |
1160 ms |
1824 KB |
Output is partially correct |
| 22 |
Partially correct |
1138 ms |
1792 KB |
Output is partially correct |
| 23 |
Partially correct |
1791 ms |
1844 KB |
Output is partially correct |
| 24 |
Correct |
6 ms |
1696 KB |
Output is correct |
| 25 |
Correct |
11 ms |
1760 KB |
Output is correct |
| 26 |
Correct |
15 ms |
1708 KB |
Output is correct |
| 27 |
Correct |
8 ms |
1724 KB |
Output is correct |
| 28 |
Correct |
11 ms |
1780 KB |
Output is correct |
| 29 |
Correct |
18 ms |
1780 KB |
Output is correct |
| 30 |
Correct |
36 ms |
1700 KB |
Output is correct |
