| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 590965 | tutis | Flight to the Ford (BOI22_communication) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll prob = 1;
#include "communication.h"
ll dec3(ll x)//4 bit x
{
vector<ll>ger;
for (ll m = 0; m < 16; m++)
{
bool ok = true;
ll v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
ll V[4] = {0, 0, 6, 9};
for (ll i = 1; i <= 3; i++)
{
bool ok = true;
for (ll j : ger)
if (x == (V[i] ^ j))
ok = false;
if (ok)
return i;
}
assert(false);
return 0;
}
ll enc3(ll X)
{
ll v = 0;
if (X == 1)
v = 0;
else if (X == 2)
v = 6;
else if (X == 3)
v = 9;
ll val = 0;
for (ll 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",
};
ll conv4(ll i)
{
ll v = 0;
ll p = 1;
for (char c : S4[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
ll conv6(ll i)
{
ll v = 0;
ll p = 1;
for (char c : S6[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
ll conv8(ll i)
{
ll v = 0;
ll p = 1;
for (char c : S8[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
bitset<8> dec8(ll x)//6 bit x
{
vector<ll>ger;
for (ll m = 0; m < 64; m++)
{
bool ok = true;
ll v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
bitset<8>ret;
for (ll i = 0; i < 8; i++)
{
for (ll j : ger)
if (x == (conv8(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<6> dec6(ll x)//5 bit x
{
vector<ll>ger;
for (ll m = 0; m < 32; m++)
{
bool ok = true;
ll v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
bitset<6>ret;
for (ll i = 0; i < 6; i++)
{
for (ll j : ger)
if (x == (conv6(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<4> dec4(ll x)//4 bit x
{
vector<ll>ger;
for (ll m = 0; m < 16; m++)
{
bool ok = true;
ll v = m;
while (v != 0)
{
if (v % 4 == 3)
ok = false;
v /= 2;
}
if (ok)
ger.push_back(m);
}
bitset<4>ret;
for (ll i = 0; i < 4; i++)
{
for (ll j : ger)
if (x == (conv4(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<4> enc4(ll X)
{
ll v = conv4(X);
ll val = 0;
for (ll t = 0; t < 4; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec4(val);
assert(ret[X] == true);
return ret;
}
bitset<8> enc8(ll X)
{
ll v = conv8(X);
ll val = 0;
for (ll 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(ll X)
{
ll v = conv6(X);
ll val = 0;
for (ll t = 0; t < 5; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec6(val);
assert(ret[X] == true);
return ret;
}
void encode(ll N, ll X)
{
if (N < 3)
return;
if (N == 3)
{
enc3(X);
return;
}
if (N >= 4)
{
ll v = N / 4;
ll vv = (X - 1) / v;
vv = min(vv, 3ll);
bitset<4>gal = enc4(vv);
ll sz[4] = {v, v, v, N - 3 * v};
ll s = 0;
for (ll 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)
{
ll v = N / 8;
ll vv = (X - 1) / v;
vv = min(vv, 7ll);
bitset<8>gal = enc8(vv);
ll sz[8] = {v, v, v, v, v, v, v, N - 7 * v};
ll s = 0;
for (ll 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)
{
ll v = N / 6;
ll vv = (X - 1) / v;
vv = min(vv, 5ll);
bitset<6>gal = enc6(vv);
ll sz[6] = {v, v, v, v, v, N - 5 * v};
ll s = 0;
for (ll i = 0; i < 6; i++)
{
if (gal[i])
{
s += sz[i];
}
else if (i < vv)
X -= sz[i];
}
encode(s, X);
return;
}
ll v = N / 3;
ll vv = 3;
if (X <= v)
vv = 1;
else if (X <= 2 * v)
vv = 2;
ll 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<ll, ll> decode(ll N)
{
if (N == 1)
return {1, 1};
if (N == 2)
return {1, 2};
if (N == 3)
{
ll val = 0;
for (ll t = 0; t < 4; t++)
val += receive() << t;
ll v = dec3(val);
pair<ll, ll>ans = {1, 2};
if (v == 1)
ans.first = 3;
if (v == 2)
ans.second = 3;
return ans;
}
else if (N >= 4)
{
ll re = 0;
for (ll t = 0; t < 4; t++)
re += receive() << t;
bitset<4> gal = dec4(re);
ll v = N / 4;
ll sz[4] = {v, v, v, N - 3 * v};
ll s = 0;
for (ll i = 0; i < 4; i++)
if (gal[i])
s += sz[i];
pair<ll, ll>r = decode(s);
ll sum = 0;
bool ger1 = false;
bool ger2 = false;
for (ll i = 0; i < 4; i++)
{
if (gal[i])
{
if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
{
for (ll 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 (ll j = 0; j < i; j++)
if (gal[j] == false)
r.second += sz[j];
ger2 = true;
}
sum += sz[i];
}
}
return r;
}
else if (N >= 8)
{
ll re = 0;
for (ll t = 0; t < 6; t++)
re += receive() << t;
bitset<8> gal = dec8(re);
ll v = N / 8;
ll sz[8] = {v, v, v, v, v, v, v, N - 7 * v};
ll s = 0;
for (ll i = 0; i < 8; i++)
if (gal[i])
s += sz[i];
pair<ll, ll>r = decode(s);
ll sum = 0;
bool ger1 = false;
bool ger2 = false;
for (ll i = 0; i < 8; i++)
{
if (gal[i])
{
if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
{
for (ll 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 (ll j = 0; j < i; j++)
if (gal[j] == false)
r.second += sz[j];
ger2 = true;
}
sum += sz[i];
}
}
return r;
}
else if (N >= 6)
{
ll re = 0;
for (ll t = 0; t < 5; t++)
re += receive() << t;
bitset<6> gal = dec6(re);
ll v = N / 6;
ll sz[6] = {v, v, v, v, v, N - 5 * v};
ll s = 0;
for (ll i = 0; i < 6; i++)
if (gal[i])
s += sz[i];
pair<ll, ll>r = decode(s);
ll sum = 0;
bool ger1 = false;
bool ger2 = false;
for (ll i = 0; i < 6; i++)
{
if (gal[i])
{
if (r.first > sum && r.first <= sum + sz[i] && ger1 == false)
{
for (ll 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 (ll j = 0; j < i; j++)
if (gal[j] == false)
r.second += sz[j];
ger2 = true;
}
sum += sz[i];
}
}
return r;
}
else
{
ll re = 0;
for (ll t = 0; t < 4; t++)
re += receive() << t;
ll val = dec3(re);
ll v = N / 3;
if (val == 2)
{
pair<ll, ll>r = decode(N - v);
if (r.first > v)
r.first += v;
if (r.second > v)
r.second += v;
return r;
}
if (val == 1)
{
pair<ll, ll>r = decode(N - v);
r.first += v;
r.second += v;
return r;
}
if (val == 3)
return decode(2 * v);
}
return { -1, -1};
}
const ll bitcnt = 4;
const ll bitsz = 1ll << bitcnt;
const ll cnt2 = 4;
// int main()
// {
// // vector<ll>ger;
// // for (ll m = 0; m < bitsz; m++)
// // {
// // bool ok = true;
// // ll v = m;
// // while (v != 0)
// // {
// // if (v % 4 == 3)
// // ok = false;
// // v /= 2;
// // }
// // if (ok)
// // ger.push_back(m);
// // }
// // bitset<bitsz>gal[bitsz];
// // for (ll m = 0; m < bitsz; m++)
// // for (ll v : ger)
// // gal[m][m ^ v] = true;
// // ll v[100];
// // v[0] = 0;
// // ll rec = 5000;
// // mt19937_64 rng(0);
// // for (ll tst = 0; tst < 10000000; tst++) {
// // for (ll i = 0; i < cnt2 / 2; i++)
// // v[i] = rng() % bitsz;
// // for (ll i = cnt2 - 1; i >= cnt2 / 2; i--)
// // v[i] = v[cnt2 - 1 - i] ^ (bitsz - 1);
// // ll mx = 0;
// // for (ll i = 0; i < cnt2; i++)
// // {
// // for (ll m : ger)
// // {
// // ll cnt = 0;
// // ll rec = v[i] ^ m;
// // for (ll 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 (ll t = 0; t < cnt2; t++)
// // cout << bitset<bitcnt>(v[t]) << endl;
// // cout << endl;
// // rec = mx;
// // }
// // }
// // return 0;
// for (ll t = 0; t < 1000; t++)
// {
// ll N = 4;
// ll val = (t % N) + 1;
// encode(N, val);
// pair<ll, ll>v = decode(N);
// cout << v.first << " " << v.second << endl;
// assert(v.first == val || v.second == val);
// }
// }