#include "Anna.h"
#include <bits/stdc++.h>
using i64 = long long;
namespace {
void SendInt(i64 x, int n) {
for (int i = 0; i < n; ++i) {
Send(x >> i & 1);
}
}
} // namespace
void Anna(int N, std::vector<char> S) {
int seen = -1;
std::vector<int> bit;
for (int i = 0; i < N; ++i) {
if (S[i] == 'X') {
if (seen == -1) {
seen = i;
bit.emplace_back(1);
bit.emplace_back(0);
} else {
bit.emplace_back(0);
}
} else {
if (seen == -1) {
bit.emplace_back(0);
} else {
if (S[i] == 'Z') {
if (i == N - 1 || S[i + 1] != 'Z') {
bit.emplace_back(1);
} else {
bit.emplace_back(0);
}
} else {
bit.emplace_back(0);
}
}
}
}
const int M = 80;
std::vector<i64> fib(M + 1);
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i <= M; ++i) {
fib[i] = fib[i - 1] + fib[i - 2];
// std::cerr << i << ' ' << fib[i] << ' ' << int(1E5 + i) / i * (std::__lg(fib[i]) + 1) << '\n';
}
const int A = 76, B = std::__lg(fib[A]) + 1;
while (bit.size() % A != 0) {
bit.emplace_back(0);
}
// for (int i = 0; i < int(bit.size()); ++i) {
// std::cout << bit[i] << " \n"[i == int(bit.size()) - 1];
// }
for (int i = 0; i < bit.size(); i += A) {
i64 x = 0;
for (int j = 0; j < A; ++j) {
if (bit[i + j]) {
x += fib[j];
}
}
// std::cout << "Anna: " << x << '\n';
SendInt(x, B);
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using i64 = long long;
namespace {
} // namespace
void Bruno(int N, int L, std::vector<int> V) {
const int M = 80;
std::vector<i64> fib(M + 1);
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i <= M; ++i) {
fib[i] = fib[i - 1] + fib[i - 2];
// std::cerr << i << ' ' << fib[i] << ' ' << int(1E5 + i - 1) / i * (std::__lg(fib[i]) + 1) << '\n';
}
const int A = 76, B = std::__lg(fib[A]) + 1;
std::vector<int> bit;
for (int i = 0, k = 0; k < L; i += A, k += B) {
i64 x = 0;
for (int j = 0; j < B; ++j) {
if (V[k + j]) {
x += 1LL << j;
}
}
// std::cout << "Bruno: " << x << '\n';
for (int j = A - 1; j >= 0; --j) {
if (x >= fib[j]) {
bit.emplace_back(1);
x -= fib[j];
} else {
bit.emplace_back(0);
}
}
std::reverse(bit.end() - A, bit.end());
}
// for (int i = 0; i < int(bit.size()); ++i) {
// std::cout << bit[i] << " \n"[i == int(bit.size()) - 1];
// }
bool seen = false;
std::vector<char> P(N);
for (int i = 0, j = 0; i < N; ++i, ++j) {
if (bit[j] == false) {
P[i] = 'Y';
} else {
if (!seen) {
seen = true;
P[i] = 'X';
j++;
} else {
P[i] = 'Z';
}
}
}
// for (int i = 0; i < N; ++i) {
// std::cout << P[i] << " \n"[i == N - 1];
// }
int idx = -1;
std::vector<int> stk;
for (int i = 0; i < N; ++i) {
if (P[i] == 'X') {
idx = i;
} else if (P[i] == 'Y') {
if (idx == -1) {
Remove(i);
} else {
stk.emplace_back(i);
}
} else {
std::reverse(stk.begin(), stk.end());
for (auto j : stk) {
Remove(j);
}
Remove(i);
stk.clear();
}
}
for (auto j : stk) {
Remove(j);
}
if (idx != -1) {
Remove(idx);
}
}
