#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 = 500;
#include "communication.h"
struct intervalset
{
int sz = 0;
vector<pair<int, int>>S;//sorted, disjoint
intervalset()
{
}
intervalset(int N)
{
sz = N;
S.push_back({1, N});
}
void append(pair<int, int> v)
{
sz += v.second - v.first + 1;
if (S.empty())
S.push_back(v);
else {
if (v.first > S.back().second)
{
if (v.first == S.back().second + 1)
S.back().second = v.second;
else
S.push_back(v);
}
else
{
assert(v.first >= S.back().first);
if (v.second > S.back().second) {
sz -= S.back().second - v.first + 1;
S.back().second = v.second;
}
}
}
}
pair<intervalset, intervalset> split(int k)
{ //k,sz-k
intervalset A;
intervalset B;
for (pair<int, int>i : S)
{
if (i.second - i.first + 1 <= k)
{
A.append(i);
k -= i.second - i.first + 1;
}
else if (k <= 0)
{
B.append(i);
}
else
{
A.append({i.first, i.first + k - 1});
B.append({i.first + k, i.second});
k = 0;
}
}
return {A, B};
}
int kth(int k)
{
for (pair<int, int>i : S)
{
if (i.second - i.first + 1 < k)
{
k -= i.second - i.first + 1;
}
else
{
return i.first + (k - 1);
}
}
assert(false);
return 0;
}
int kelintas(int x)
{
int r = 0;
for (pair<int, int>i : S)
{
if (i.second < x)
r += (i.second - i.first + 1);
else if (x < i.first)
return 0;
else
return r + (x - i.first + 1);
}
return 0;
}
intervalset(const intervalset &A, const intervalset &B)
{
const vector<pair<int, int>>&a = A.S;
const vector<pair<int, int>>&b = B.S;
int i = 0;
int j = 0;
while (i < (int)a.size() && j < (int)b.size())
{
if (a[i].first < b[j].first)
append(a[i++]);
else
append(b[j++]);
}
while (i < (int)a.size())
append(a[i++]);
while (j < (int)b.size())
append(b[j++]);
}
};
const int mxsum = 200;
pair<int, pair<int, int>> K[mxsum][mxsum];
bool prec = false;
pair<int, int> getbest(int A, int B)
{
if (A + B < mxsum)
{
if (prec == false)
{
prec = true;
for (int sum = 0; sum < mxsum; sum++)
for (int a = 0; a <= sum; a++)
{
int b = sum - a;
K[a][b] = {1000, {0, 0}};
}
for (int sum = 0; sum < mxsum; sum++)
{
if (sum <= 2)
{
for (int a = 0; a <= sum; a++) {
int b = sum - a;
K[a][b] = {0, {0, 0}};
}
}
else {
bool rep = true;
while (rep)
{
rep = false;
for (int a = 0; a <= sum; a++)
{
int b = sum - a;
for (int a0 = 0; a0 <= a; a0++)
{
for (int b0 = 0; b0 <= b; b0++)
{
int a1 = a - a0;
int b1 = b - b0;
int a_ = a0 + b0;
int b_ = a1;
int a__ = a1 + b1;
int b__ = a0;
int g = 1 + max(K[a_][b_].first, K[a__][b__].first);
if (K[a][b].first > g)
{
K[a][b] = {g, {a0, b0}};
rep = true;
}
}
}
}
}
}
}
}
return K[A][B].second;
}
else
{
return {A / 2, B / 2};
}
}
vector<pair<int, int>>eil;
void encode(int N, int X)
{
intervalset A(N);
intervalset B;
mt19937 rng(0);
while (A.sz + B.sz > 2)
{
eil.push_back({A.sz, B.sz});
pair<int, int>c = getbest(A.sz, B.sz);
int a0 = c.first;
int b0 = c.second;
eil.push_back({a0, b0});
eil.push_back({0, 0});
intervalset C(A, B);
int ka = A.kelintas(X);
int kb = B.kelintas(X);
int s = 1;
if (ka != 0 && ka <= a0)
s = 0;
if (kb != 0 && kb <= b0)
s = 0;
pair<intervalset, intervalset>A_ = A.split(a0);
pair<intervalset, intervalset>B_ = B.split(b0);
int r = send(s);
if (r == 0)
{
A = intervalset(A_.first, B_.first);
B = A_.second;
}
else
{
A = intervalset(A_.second, B_.second);
B = A_.first;
}
}
}
pair<int, int> decode(int N)
{
intervalset A(N);
intervalset B;
mt19937 rng(0);
while (A.sz + B.sz > 2)
{
pair<int, int>c = getbest(A.sz, B.sz);
int a0 = c.first;
int b0 = c.second;
pair<intervalset, intervalset>A_ = A.split(a0);
pair<intervalset, intervalset>B_ = B.split(b0);
int r = receive();
if (r == 0)
{
A = intervalset(A_.first, B_.first);
B = A_.second;
}
else
{
A = intervalset(A_.second, B_.second);
B = A_.first;
}
}
if (A.sz == 0)
return {B.S[0].first, B.S.back().second};
if (B.sz == 0)
return {A.S[0].first, A.S.back().second};
return {A.S[0].first, B.S[0].first};
}
// int main()
// {
// int mx = 0;
// vector<pair<int, int>>ilg;
// for (int test = 0; test < 100; test++)
// {
// int N = 3 + asdasdasdasdasd() % ((int)1e9 - 3 + 1);
// int X = (asdasdasdasdasd() % N) + 1;
// encode(N, X);
// pair<int, int>a = decode(N);
// assert(a.first >= 1 && a.first <= N && a.second >= 1 && a.second <= N);
// assert(a.first == X || a.second == X);
// if (kiekis > mx)
// {
// ilg = eil;
// mx = kiekis;
// }
// if (test % 10 == 0)
// cout << kiekis << endl;
// kiekis = 0;
// eil.clear();
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
357 ms |
2708 KB |
Output is correct |
| 2 |
Correct |
407 ms |
2616 KB |
Output is correct |
| 3 |
Correct |
376 ms |
2740 KB |
Output is correct |
| 4 |
Correct |
354 ms |
2632 KB |
Output is correct |
| 5 |
Correct |
401 ms |
2608 KB |
Output is correct |
| 6 |
Correct |
886 ms |
3620 KB |
Output is correct |
| 7 |
Correct |
383 ms |
2696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1160 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
803 ms |
3312 KB |
Output is correct |
| 3 |
Correct |
722 ms |
3784 KB |
Output is correct |
| 4 |
Correct |
1190 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
1111 ms |
3800 KB |
Output is correct |
| 6 |
Correct |
1023 ms |
3800 KB |
Output is correct |
| 7 |
Correct |
2744 ms |
8004 KB |
Output is correct |
| 8 |
Correct |
5080 ms |
14564 KB |
Output is correct |
| 9 |
Correct |
4154 ms |
11148 KB |
Output is correct |
| 10 |
Correct |
4339 ms |
11236 KB |
Output is correct |
| 11 |
Correct |
3937 ms |
10952 KB |
Output is correct |
| 12 |
Correct |
4205 ms |
11168 KB |
Output is correct |
| 13 |
Correct |
4015 ms |
11188 KB |
Output is correct |
| 14 |
Correct |
4091 ms |
11144 KB |
Output is correct |
| 15 |
Correct |
2309 ms |
8104 KB |
Output is correct |
| 16 |
Correct |
3912 ms |
12352 KB |
Output is correct |
| 17 |
Correct |
1651 ms |
5960 KB |
Output is correct |
| 18 |
Correct |
1547 ms |
6056 KB |
Output is correct |
| 19 |
Correct |
1599 ms |
6192 KB |
Output is correct |
| 20 |
Correct |
1543 ms |
5948 KB |
Output is correct |
| 21 |
Correct |
1588 ms |
6192 KB |
Output is correct |
| 22 |
Correct |
1486 ms |
5820 KB |
Output is correct |
| 23 |
Correct |
1959 ms |
6116 KB |
Output is correct |
| 24 |
Correct |
407 ms |
2600 KB |
Output is correct |
| 25 |
Correct |
423 ms |
2612 KB |
Output is correct |
| 26 |
Correct |
358 ms |
2624 KB |
Output is correct |
| 27 |
Correct |
362 ms |
2600 KB |
Output is correct |
| 28 |
Correct |
349 ms |
2608 KB |
Output is correct |
| 29 |
Correct |
854 ms |
3668 KB |
Output is correct |
| 30 |
Correct |
437 ms |
2596 KB |
Output is correct |
