#pragma GCC optimize ("O3")
#pragma GCC target("avx,avx2,fma")
#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 = 30;
int bitcnt1 = 14;
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;
}
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)
{
if (N < 3)
return;
if (N == 3)
{
enc3(X);
return;
}
for (int bc = bitcnt; bc >= 6; bc--)
if (N >= (1 << bc))
{
if (N % (1 << bc) != 0)
{
int v = -N % (1 << bc);
v += (1 << bc);
N += v;
}
int v = N / (1 << bc);
int vv = (X - 1) / v;
vv = min(vv, (1 << bc) - 1);
bitcnt1 = bc;
int gal1 = encB(vv);
int s = 0;
s = v * getL(bc);
X -= vv * v;
X += cntT(vv, bc, gal1) * v;
encode(s, X);
return;
}
if (N >= 4)
{
while (N % 4 != 0)
N++;
int v = N / 4;
int vv = (X - 1) / v;
vv = min(vv, 3);
bitset<4>gal = enc4(vv);
int s = 0;
for (int i = 0; i < 4; i++)
{
if (gal[i])
{
s += v;
}
else if (i < vv)
X -= v;
}
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;
}
for (int bc = bitcnt; bc >= 6; bc--)
if (N >= (1 << bc))
{
int N1 = N;
if (N % (1 << bc) != 0)
{
int v = -N % (1 << bc);
v += (1 << bc);
N += v;
}
int re = 0;
for (int t = 0; t < bc; t++)
re += receive() << t;
int v = N / (1 << bc);
int s = getL(bc) * v;
pair<int, int>r = decode(s);
int i1 = kth((r.first - 1) / v, bc, re);
int i2 = kth((r.second - 1) / v, bc, re);
r.first += v * (i1 - cntT(i1, bc, re));
r.second += v * (i2 - cntT(i2, bc, re));
r.first = min(r.first, N1);
r.second = min(r.second, N1);
return r;
}
if (N >= 4)
{
int N1 = N;
while (N % 4 != 0)
N++;
int re = 0;
for (int t = 0; t < 4; t++)
re += receive() << t;
bitset<4> gal = dec4(re);
int v = N / 4;
int s = 0;
for (int i = 0; i < 4; i++)
if (gal[i])
s += v;
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 + v && ger1 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.first += v;
ger1 = true;
}
if (r.second > sum && r.second <= sum + v && ger2 == false)
{
for (int j = 0; j < i; j++)
if (gal[j] == false)
r.second += v;
ger2 = true;
}
sum += v;
}
}
r.first = min(r.first, N1);
r.second = min(r.second, N1);
return r;
}
return { -1, -1};
}
// int main()
// {
// for (int t = 0; t < 1000; t++)
// {
// int N = 1e9;
// 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);
// }
// }
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
1688 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1784 KB |
Output is correct |
| 3 |
Correct |
17 ms |
1720 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1740 KB |
Output is correct |
| 5 |
Correct |
11 ms |
1680 KB |
Output is correct |
| 6 |
Correct |
27 ms |
1860 KB |
Output is correct |
| 7 |
Correct |
55 ms |
1680 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
699 ms |
1664 KB |
Output is partially correct |
| 2 |
Partially correct |
249 ms |
1884 KB |
Output is partially correct |
| 3 |
Partially correct |
496 ms |
1668 KB |
Output is partially correct |
| 4 |
Partially correct |
871 ms |
1744 KB |
Output is partially correct |
| 5 |
Partially correct |
599 ms |
1684 KB |
Output is partially correct |
| 6 |
Partially correct |
663 ms |
1744 KB |
Output is partially correct |
| 7 |
Partially correct |
1885 ms |
1808 KB |
Output is partially correct |
| 8 |
Partially correct |
3132 ms |
1964 KB |
Output is partially correct |
| 9 |
Partially correct |
2965 ms |
1960 KB |
Output is partially correct |
| 10 |
Partially correct |
2728 ms |
1884 KB |
Output is partially correct |
| 11 |
Partially correct |
2621 ms |
1960 KB |
Output is partially correct |
| 12 |
Partially correct |
2675 ms |
1948 KB |
Output is partially correct |
| 13 |
Partially correct |
2848 ms |
1960 KB |
Output is partially correct |
| 14 |
Partially correct |
3074 ms |
1960 KB |
Output is partially correct |
| 15 |
Partially correct |
1707 ms |
1800 KB |
Output is partially correct |
| 16 |
Partially correct |
3757 ms |
1924 KB |
Output is partially correct |
| 17 |
Partially correct |
713 ms |
1752 KB |
Output is partially correct |
| 18 |
Partially correct |
888 ms |
1724 KB |
Output is partially correct |
| 19 |
Partially correct |
738 ms |
1832 KB |
Output is partially correct |
| 20 |
Partially correct |
723 ms |
1872 KB |
Output is partially correct |
| 21 |
Partially correct |
695 ms |
1780 KB |
Output is partially correct |
| 22 |
Partially correct |
907 ms |
1836 KB |
Output is partially correct |
| 23 |
Partially correct |
1520 ms |
1732 KB |
Output is partially correct |
| 24 |
Correct |
13 ms |
1728 KB |
Output is correct |
| 25 |
Correct |
12 ms |
1812 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1804 KB |
Output is correct |
| 27 |
Correct |
12 ms |
1692 KB |
Output is correct |
| 28 |
Correct |
12 ms |
1836 KB |
Output is correct |
| 29 |
Correct |
20 ms |
1764 KB |
Output is correct |
| 30 |
Correct |
44 ms |
1740 KB |
Output is correct |
