/* https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/shopping-review.pdf */
#include "Anna.h"
#include <cassert>
#include <vector>
using namespace std;
namespace A {
const int N = 1000000, A = 18, B = 300, D = 14, INF = 0x3f3f3f3f;
int ql, qr, a, k, l, x, l1, r1, l2, r2, i_, zz[(N + 1) * 2], dd[N + 1], n, m;
int lg(int n) {
int l = 0;
while (1 << l < n)
l++;
return l;
}
void check() {
int good = 1;
for (int d = 0; d <= D; d++) {
int a = A - (d == 0 ? 3 : 4) - d, b = 0, n = N;
for (int h = 0; h < d; h++)
n /= 2;
for (int h = 0; h < a; h++) {
n = (n + 1) / 2;
b += lg(n / 2 + 1);
}
b += lg(N + 1) + (n + 1) * 2;
if (b > B)
good = 0;
}
assert(good);
}
int idx(int i) {
if (i < l1)
return i - l2;
else if (i <= r1)
return l1 - l2;
else
return l1 - l2 + i - r1;
}
void get_tree(int l, int r, int d) {
if (l < r) {
int i, c;
for (i = l + 1, c = 1; i < r && c > 0; i++)
c += zz[i] == 0 ? 1 : -1;
get_tree(l + 1, i - 1, d + 1);
dd[n++] = d;
get_tree(i, r, d + 1);
}
}
}
void InitA(int n, int ql_, int qr_) {
A::check();
A::ql = ql_, A::qr = qr_, A::a = A::A;
int d = 0, l = 0, r = A::N - 1, x = 0;
while (1) {
int m = (l + r) / 2;
if (d >= A::D || A::ql <= m && m <= A::qr) {
A::l1 = m + 1, A::r1 = m, A::l2 = l, A::r2 = r;
break;
}
if (A::qr < m)
r = m - 1, x = x << 1 | 0;
else
l = m + 1, x = x << 1 | 1;
d++;
}
d += A::D + 1;
for (int h = A::lg(d + 1) - 2; h >= 0; h--)
SendA(d >> h & 1), A::a--;
d -= A::D + 1;
for (int h = d - 1; h >= 0; h--)
SendA(x >> h & 1), A::a--;
if (A::a > 0)
A::k = (A::l1 - A::l2 + A::r2 - A::r1) / 2, A::l = A::lg(A::k + 1), A::x = 0, A::i_ = 0;
else
A::l = A::lg(A::N + 1);
}
void ReceiveA(bool z) {
if (A::a > 0) {
A::x = A::x << 1 | z;
if (--A::l == 0) {
int l_ = A::l1 - A::x, r_ = A::r1 + A::k - A::x, z = l_ <= A::ql && A::qr <= r_ ? 0 : 1;
SendA(z), A::a--;
if (z == 0)
A::l2 = l_, A::r2 = r_;
else
A::l1 = l_, A::r1 = r_;
if (A::a > 0)
A::k = (A::l1 - A::l2 + A::r2 - A::r1) / 2, A::l = A::lg(A::k + 1), A::x = 0;
else
A::l = A::lg(A::N + 1);
}
} else if (A::l > 0)
A::i_ = A::i_ << 1 | z, A::l--;
else
A::zz[A::m++] = z;
}
int Answer() {
int l = A::idx(A::ql), r = A::idx(A::qr);
A::get_tree(0, A::m, 0);
int i1 = -1;
for (int i = l; i <= r; i++)
if (i1 == -1 || A::dd[i1] > A::dd[i])
i1 = i;
return i1 == A::l1 - A::l2 ? A::i_ : (i1 < A::l1 - A::l2 ? i1 + A::l2 : i1 + A::l2 + A::r1 - A::l1);
}
/* https://www.ioi-jp.org/camp/2021/2021-sp-tasks/day2/shopping-review.pdf */
#include "Bruno.h"
#include <vector>
using namespace std;
namespace B {
const int N = 1000000, A = 18, B = 300, D = 14, INF = 0x3f3f3f3f;
int aa[N], aa_[N + 1], ll[N + 1], rr[N + 1], mode, d, l, r, a, lower, upper, mid;
int lg(int n) {
int l = 0;
while (1 << l < n)
l++;
return l;
}
void send_tree(int *aa, int n) {
if (n > 0) {
int i_ = -1;
for (int i = 0; i < n; i++)
if (i_ == -1 || aa[i_] > aa[i])
i_ = i;
SendB(0);
if (i_ > 0)
send_tree(aa, i_);
SendB(1);
if (i_ + 1 < n)
send_tree(aa + i_ + 1, n - 1 - i_);
}
}
void send() {
if (a > 0) {
mid = (lower + upper) / 2;
int x = ll[lower] - ll[mid], l = lg(mid - lower + 1);
for (int h = l - 1; h >= 0; h--)
SendB(x >> h);
} else {
int i_ = N;
for (int i = ll[lower]; i <= rr[lower]; i++)
if (i_ == N || aa[i_] > aa[i])
i_ = i;
int l = lg(N + 1);
for (int h = l - 1; h >= 0; h--)
SendB(i_ >> h);
int n = 0;
for (int i = ll[upper]; i < ll[lower]; i++)
aa_[n++] = aa[i];
aa_[n++] = i_ == N ? N : aa[i_];
for (int i = rr[lower] + 1; i <= rr[upper]; i++)
aa_[n++] = aa[i];
send_tree(aa_, n);
}
}
void init() {
int m = (l + r) / 2;
ll[0] = m + 1, rr[0] = m, ll[1] = m, rr[1] = m;
for (int k = 2; k <= r - l + 1; k++) {
ll[k] = ll[k - 1], rr[k] = rr[k - 1];
if (rr[k] == r || ll[k] > l && aa[ll[k] - 1] > aa[rr[k] + 1])
ll[k]--;
else
rr[k]++;
}
lower = 0, upper = r - l + 1, send();
}
}
typedef vector<int> vi;
void InitB(int n, vi pp) {
B::mode = 0;
for (int i = 0; i < n; i++)
B::aa[i] = pp[i];
for (int i = n; i < B::N; i++)
B::aa[i] = i + 1;
B::d = 1, B::l = 0, B::r = B::N - 1, B::a = B::A;
}
void ReceiveB(bool z) {
B::a--;
if (B::mode == 0) {
B::d = B::d << 1 | z;
if (B::d > B::D) {
B::d -= B::D + 1, B::mode = 1;
if (B::d == 0)
B::init(), B::mode = 2;
}
} else if (B::mode == 1) {
int m = (B::l + B::r) / 2;
if (z == 0)
B::r = m - 1;
else
B::l = m + 1;
if (--B::d == 0)
B::init(), B::mode = 2;
} else {
if (z == 0)
B::upper = B::mid;
else
B::lower = B::mid;
B::send();
}
}
Compilation message
Anna.cpp: In function 'void InitA(int, int, int)':
Anna.cpp:59:31: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
59 | if (d >= A::D || A::ql <= m && m <= A::qr) {
| ~~~~~~~~~~~^~~~~~~~~~~~~
Bruno.cpp: In function 'void B::init()':
Bruno.cpp:58:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
58 | if (rr[k] == r || ll[k] > l && aa[ll[k] - 1] > aa[rr[k] + 1])
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4500 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4368 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4368 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
200 KB |
Wrong Answer [1] |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4456 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4500 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4368 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4368 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
200 KB |
Wrong Answer [1] |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
268 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
