| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 591779 | 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.
#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
int prob = 50;
#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] = {"110",
"100",
"011",
"010",
"001",
"000"
};
string S10[10] = {"110000",
"100010",
"100001",
"011110",
"011011",
"010111",
"010100",
"001101",
"001000",
"000110"
};
int conv10(int i)
{
int v = 0;
int p = 1;
for (char c : S10[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
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;
}
string S5[5] = {"00",
"00",
"01",
"11",
"10"
};
string S9[9] = {"00",
"00",
"01",
"01",
"01",
"11",
"11",
"10",
"10"
};
int conv5(int i)
{
int v = 0;
int p = 1;
for (char c : S5[i])
{
if (c == '1')
v += p;
p *= 2;
}
return v;
}
int conv9(int i)
{
int v = 0;
int p = 1;
for (char c : S9[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<5> dec5(int x)//2 bit x
{
vector<int>ger;
for (int m = 0; m < 4; 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<5>ret;
for (int i = 0; i < 5; i++)
{
for (int j : ger)
if (x == (conv5(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<9> dec9(int x)//3 bit x
{
vector<int>ger;
for (int m = 0; m < 8; 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<9>ret;
for (int i = 0; i < 9; i++)
{
for (int j : ger)
if (x == (conv9(i) ^ j))
ret[i] = true;
}
return ret;
}
bitset<6> dec6(int x)//3 bit x
{
vector<int>ger;
for (int m = 0; m < 8; 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<10> dec10(int x)//6 bit x
{
vector<int>ger;
for (int m = 0; m < (1 << 6); 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<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<5> enc5(int X)
{
int v = conv5(X);
int val = 0;
for (int t = 0; t < 2; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec5(val);
assert(ret[X] == true);
return ret;
}
bitset<9> enc9(int X)
{
int v = conv9(X);
int val = 0;
for (int t = 0; t < 3; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec9(val);
assert(ret[X] == true);
return ret;
}
bitset<6> enc6(int X)
{
int v = conv6(X);
int val = 0;
for (int t = 0; t < 3; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
auto ret = dec6(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;
}
const int bitcnt = 30;
const int mincnt = 5;
int bitcnt1 = 14;
float ups = 0.99;
int encB(int v)
{
int val = 0;
for (int t = 0; t < bitcnt1; t++)
{
val += (send(v % 2) << t);
v /= 2;
}
return val;
}
int C[40][2];
bool prec = false;
int getL(int l)
{
if (prec == false)
{
C[0][0] = 1;
for (int i = 1; i < 40; i++)
{
C[i][0] = C[i - 1][0] + C[i - 1][1];
C[i][1] = C[i - 1][0];
}
prec = true;
}
return C[l][0] + C[l][1];
}
int cntT(int m, int l, int g, int x = 0)
{
if (prec == false)
{
C[0][0] = 1;
for (int i = 1; i < 40; i++)
{
C[i][0] = C[i - 1][0] + C[i - 1][1];
C[i][1] = C[i - 1][0];
}
prec = true;
}
if (m == (1 << l))
{
return C[l][0] + C[l][1];
}
int ret = 0;
for (int b = l; b >= 1; b--)
{
int vv = m & (1 << (b - 1));
int gg = g & (1 << (b - 1));
m -= vv;
g -= gg;
vv /= (1 << (b - 1));
gg /= (1 << (b - 1));
int f1 = -1;
for (int nxt : {0, 1}) {
int f = gg ^ nxt;
if (f == 1 && x == 1)
continue;
if (nxt < vv)
ret += C[b][f];
else if (nxt == vv)
f1 = f;
}
if (f1 == -1)
break;
x = f1;
}
return ret;
}
int kth(int k, int l, int g, int x = 0)
{
if (l == 0)
return 0;
if (prec == false)
{
C[0][0] = 1;
for (int i = 1; i < 40; i++)
{
C[i][0] = C[i - 1][0] + C[i - 1][1];
C[i][1] = C[i - 1][0];
}
prec = true;
}
int s = 0;
for (int b = l; b >= 1; b--)
{
int gg = g & (1 << (b - 1));
g -= gg;
gg /= (1 << (b - 1));
for (int nxt : {0, 1})
{
int f = gg ^ nxt;
if (f == 1 && x == 1)
continue;
if (k < C[b][f])
{
s += ((1 << (b - 1)) * nxt);
x = f;
break;
}
else
k -= C[b][f];
}
}
return s;
}
void encode(int N, int X, bool fst = true)
{
if (fst)
X += 18891198;
X %= N;
if (X == 0)
X += N;
if (N < 3)
return;
if (N == 3)
{
enc3(X);
encode(2, 0, false);
return;
}
if (false)
if (N == 9)
{
int sz[9];
for (int i = 0; i < 9; i++)
sz[i] = 1;
int vv = 0;
{
int XX = X;
while (XX > sz[vv])
{
XX -= sz[vv];
vv++;
}
}
bitset<9>gal = enc9(vv);
int s = 0;
for (int i = 0; i < 9; i++)
{
if (gal[i])
{
s += sz[i];
}
else if (i < vv)
X -= sz[i];
}
encode(s, X, false);
return;
}
if (N == 5)
{
int sz[5];
for (int i = 0; i < 5; i++)
sz[i] = 1;
int vv = 0;
{
int XX = X;
while (XX > sz[vv])
{
XX -= sz[vv];
vv++;
}
}
bitset<5>gal = enc5(vv);
int s = 0;
for (int i = 0; i < 5; i++)
{
if (gal[i])
{
s += sz[i];
}
else if (i < vv)
X -= sz[i];
}
encode(s, X, false);
return;
}
if (N == 6)
{
int sz[6];
for (int i = 0; i < 6; i++)
sz[i] = 1;
int vv = 0;
{
int XX = X;
while (XX > sz[vv])
{
XX -= sz[vv];
vv++;
}
}
bitset<6>gal = enc6(vv);
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, false);
return;
}
if (N == 9 || N == 10)
{
int sz[10];
for (int i = 0; i < 10; i++)
sz[i] = 1;
int vv = 0;
{
int XX = X;
while (XX > sz[vv])
{
XX -= sz[vv];
vv++;
}
}
bitset<10>gal = enc10(vv);
if (N == 9)
gal[9] = false;
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, false);
return;
}
for (int bc = bitcnt; bc >= mincnt; bc--)
if (N >= (1 << bc) * ups)
{
N = max(N, 1 << bc);
int v = N / (1 << bc);
int k1 = N % (1 << bc);
int k0 = (1 << bc) - k1;
assert(k0 * v + k1 * (v + 1) == N);
int vv = (X - 1) / v;
if (vv >= k0)
vv = k0 + (X - k0 * v - 1) / (v + 1);
assert(X >= 1 && X <= N);
assert(vv >= 0 && vv < (1 << bc));
bitcnt1 = bc;
int gal1 = encB(vv);
int c1 = getL(bc);
int kk0 = cntT(k0, bc, gal1);
int s = (v + 1) * c1 - kk0;
int c = cntT(vv, bc, gal1);
if (X <= k0 * v + v + 1)
{
X -= (vv - c) * v;
}
else
{
X -= vv * (v + 1) - k0;
X += c * (v + 1) - kk0;
}
encode(s, X, false);
return;
}
if (N >= 4)
{
int sz[4];
for (int i = 0; i < 4; i++)
sz[i] = N / 4;
for (int i = 0; i < (N % 4); i++)
sz[i]++;
int vv = 0;
{
int XX = X;
while (XX > sz[vv])
{
XX -= sz[vv];
vv++;
}
}
bitset<4>gal = enc4(vv);
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, false);
return;
}
}
void ch(pair<int, int>&a, int N)
{
a.first -= 18891198;
a.second -= 18891198;
a.first %= N;
a.second %= N;
if (a.first <= 0)
a.first += N;
if (a.second <= 0)
a.second += N;
}
pair<int, int> decode(int N, bool fst = true)
{
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;
if (fst)
ch(ans, N);
return ans;
}
if (false)
if (N == 9)
{
int re = 0;
for (int t = 0; t < 3; t++)
re += receive() << t;
bitset<9> gal = dec9(re);
int sz[9];
for (int i = 0; i < 9; i++)
sz[i] = 1;
int s = 0;
for (int i = 0; i < 9; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s, false);
int sum = 0;
bool ger1 = false;
bool ger2 = false;
for (int i = 0; i < 9; 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];
}
}
if (fst)
ch(r, N);
return r;
}
if (N == 5)
{
int re = 0;
for (int t = 0; t < 2; t++)
re += receive() << t;
bitset<5> gal = dec5(re);
int sz[5];
for (int i = 0; i < 5; i++)
sz[i] = 1;
int s = 0;
for (int i = 0; i < 5; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s, false);
int sum = 0;
bool ger1 = false;
bool ger2 = false;
for (int i = 0; i < 5; 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];
}
}
if (fst)
ch(r, N);
return r;
}
if (N == 6)
{
int re = 0;
for (int t = 0; t < 3; t++)
re += receive() << t;
bitset<6> gal = dec6(re);
int sz[6];
for (int i = 0; i < 6; i++)
sz[i] = 1;
int s = 0;
for (int i = 0; i < 6; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s, false);
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];
}
}
if (fst)
ch(r, N);
return r;
}
if (N == 9 || N == 10)
{
int re = 0;
for (int t = 0; t < 6; t++)
re += receive() << t;
bitset<10> gal = dec10(re);
if (N == 9)
gal[9] = false;
int sz[10];
for (int i = 0; i < 10; i++)
sz[i] = 1;
int s = 0;
for (int i = 0; i < 10; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s, false);
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];
}
}
if (fst)
ch(r, N);
return r;
}
for (int bc = bitcnt; bc >= mincnt; bc--)
if (N >= (1 << bc) * ups)
{
N = max(N, 1 << bc);
int re = 0;
for (int t = 0; t < bc; t++)
re += receive() << t;
int v = N / (1 << bc);
int k1 = N % (1 << bc);
int k0 = (1 << bc) - k1;
int c1 = getL(bc);
int kk0 = cntT(k0, bc, re);
int s = (v + 1) * c1 - kk0;
pair<int, int>r = decode(s, false);
auto blo = [&](int p)->int
{
int i = (p - 1) / v;
if (i >= kk0)
i = kk0 + (p - kk0 * v - 1) / (v + 1);
return i;
};
int i1 = kth(blo(r.first), bc, re);
int i2 = kth(blo(r.second), bc, re);
if (i1 <= k0)
r.first += v * (i1 - cntT(i1, bc, re));
else
{
r.first += (k0 - kk0) * v;
r.first += (v + 1) * (i1 - cntT(i1, bc, re) - (k0 - kk0));
}
if (i2 <= k0)
r.second += v * (i2 - cntT(i2, bc, re));
else
{
r.second += (k0 - kk0) * v;
r.second += (v + 1) * (i2 - cntT(i2, bc, re) - (k0 - kk0));
}
if (fst)
ch(r, N);
return r;
}
if (N >= 4)
{
int re = 0;
for (int t = 0; t < 4; t++)
re += receive() << t;
bitset<4> gal = dec4(re);
int sz[4];
for (int i = 0; i < 4; i++)
sz[i] = N / 4;
for (int i = 0; i < (N % 4); i++)
sz[i]++;
int s = 0;
for (int i = 0; i < 4; i++)
if (gal[i])
s += sz[i];
pair<int, int>r = decode(s, false);
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];
}
}
if (fst)
ch(r, N);
return r;
}
return { -1, -1};
}
// int main()
// {
// mt19937 rng(0);
// int maxi = 0;
// ld sum = 0;
// for (int t = 0; t < 50000; t++)
// {
// kiekis = 0;
// int N = 1e9;
// int val = (rng() % N) + 1;
// encode(N, val);
// pair<int, int>v = decode(N);
// //cout << v.first << " " << v.second << endl;
// assert(v.first == val || v.second == val);
// maxi = max(maxi, kiekis);
// sum += kiekis;
// }
// cout << maxi << endl;
// cout << sum / 50000 << endl;
// }