#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"
};
int conv4(int i)
{
int v = 0;
int p = 1;
for (char c : S4[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
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;
}
const int bitcnt = 15;
bitset < 1 << bitcnt > decB(int x) //4 bit x
{
vector<int>ger;
for (int m = 0; m < (1 << bitcnt); 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 < 1 << bitcnt > ret;
for (int j : ger)
ret[x ^ j] = true;
return ret;
}
bitset < 1 << bitcnt > encB(int v)
{
int val = 0;
int vv = v;
for (int t = 0; t < bitcnt; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = decB(val);
assert(ret[vv] == true);
return ret;
}
void encode(int N, int X)
{
if (N < 3)
return;
if (N == 3)
{
enc3(X);
return;
}
if (N >= (1 << bitcnt))
{
int v = N / (1 << bitcnt);
int vv = (X - 1) / v;
vv = min(vv, (1 << bitcnt) - 1);
bitset < (1 << bitcnt) > gal = encB(vv);
int sz[(1 << bitcnt)];
for (int i = 0; i < (1 << bitcnt); i++)
sz[i] = v;
sz[(1 << bitcnt) - 1] = N - v * ((1 << bitcnt) - 1);
int s = 0;
for (int i = 0; i < (1 << bitcnt); 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;
}
}
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;
}
if (N >= (1 << bitcnt))
{
int re = 0;
for (int t = 0; t < bitcnt; t++)
re += receive() << t;
bitset < (1 << bitcnt) > gal = decB(re);
int v = N / (1 << bitcnt);
int sz[(1 << bitcnt)];
for (int i = 0; i < (1 << bitcnt); i++)
sz[i] = v;
sz[(1 << bitcnt) - 1] = N - v * ((1 << bitcnt) - 1);
int s = 0;
for (int i = 0; i < (1 << bitcnt); 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 < (1 << bitcnt); 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;
}
return { -1, -1};
}
int main()
{
for (int t = 0; t < 1000; t++)
{
int N = 1000;
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);
}
}
Compilation message
/usr/bin/ld: /tmp/cc4nv7SH.o: in function `main':
interface.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuULpSE.o:communication.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
