#include "Anna.h"
#include <cstdint>
#include <vector>
void Anna(int N, std::vector<char> S) {
for (int i = 0; i < N; i += 20) {
int64_t x = 0;
for (int j = 0; j < 20; ++j) {
x = (3 * x + (i + j < N ? S[i + j] - 'X' : 0));
}
for (int bt = 31; bt >= 0; --bt) {
Send(!!(x & 1ll << bt));
}
}
}
#include "Bruno.h"
#include <algorithm>
#include <set>
#include <vector>
#include <string>
using namespace std;
void Bruno(int N, int L, std::vector<int> A) {
vector<char> a;
for (int i = 0; i < N; i += 32) {
int64_t x = 0;
for (int j = 0; j < 32; ++j) {
x = (x << 1) + A[i + j];
}
string s;
for (int bt = 0; bt < 20; ++bt) {
s.push_back('X' + (x % 3));
x /= 3;
}
reverse(s.begin(), s.end());
for (char &i : s) {
a.push_back(i);
}
}
while (a.size() > N) {
a.pop_back();
}
// everything to the left of the first X is fucked
// same for the right of the last Z
int xloc = -1;
for (int i = N - 1; i >= 0; --i) {
if (a[i] == 'X') {
xloc = i;
}
}
int zloc = -1;
for (int i = 0; i < N; ++i) {
if (a[i] == 'Z') {
zloc = i;
}
}
if (xloc == -1 || zloc == -1 || xloc > zloc) { // no X or no Z or first X occurs after last Z
for (int i = 0; i < N; ++i) {
Remove(i);
}
return;
}
for (int i = 0; i < xloc; ++i) {
Remove(i);
}
for (int i = zloc + 1; i < N; ++i) {
Remove(i);
}
int l = xloc == -1 ? 0 : xloc, r = zloc == -1 ? N - 1 : zloc;
// only a[l...r] remains with a[l] = X and a[r] = Z
// now employ a greedy strategy: we must maintain:
// - st => positions
// - st_x => positions of x
// - st_y => positions of y
// - st_z => positions of z
// then
// - good_ys => y such that an X exists to the left and a Z exists to the right with no Y's in between
// to maintain this set, we must store, for each X and Z, the good y it corresponds to
// for this, use a flat array arr[i] = {good ys that match with a[i]=X/Z}
set<int> st, st_x, st_y, st_z, good_ys;
vector<set<int>> arr(N);
for (int i = l; i <= r; ++i) {
if (i != l && a[i] == 'Y' && a[i - 1] == 'Y') {
Remove(i);
continue;
}
st.insert(i);
if (a[i] == 'X') {
st_x.insert(i);
} else if (a[i] == 'Y') {
st_y.insert(i);
} else {
st_z.insert(i);
}
}
auto y_exists_in = [&](int l, int r) {
auto itl = st_y.lower_bound(l);
if (itl == st_y.end()) {
return false;
}
return *itl <= r;
};
auto get_lef_rig = [&](int i) -> pair<int, int> {
auto it_z = st_z.lower_bound(i);
if (it_z == st_z.end()) {
return {-1, -1};
}
auto it_x = st_x.lower_bound(i);
if (it_x == st_x.begin()) {
return {-1, -1};
}
--it_x;
int lef = *it_x, rig = *it_z;
return {lef, rig};
};
auto check = [&](int i) {
good_ys.erase(i);
auto [lef, rig] = get_lef_rig(i);
if (lef == -1 || rig == -1) {
return;
}
if (y_exists_in(lef, i - 1) || y_exists_in(i + 1, rig)) {
return;
}
arr[lef].insert(i);
arr[rig].insert(i);
good_ys.insert(i);
};
for (int i = l; i <= r; ++i) {
if (a[i] != 'Y') {
continue;
}
check(i);
}
auto erase = [&](int i) {
st.erase(i);
Remove(i);
if (st_y.contains(i)) {
auto it = st_y.find(i);
int l = -1, r = -1;
if (it != st_y.begin()) {
l = *prev(it);
}
if (it != --st_y.end()) {
r = *next(it);
}
st_y.erase(it);
if (l != -1) {
check(l);
}
if (r != -1) {
check(r);
}
return;
}
st_x.erase(i);
st_z.erase(i);
for (auto &idx : arr[i]) {
check(idx);
}
arr[i].clear();
};
while (!good_ys.empty()) {
int idx = *good_ys.begin();
good_ys.erase(good_ys.begin());
auto [lef, rig] = get_lef_rig(idx);
auto next = [&](int x) { return st.lower_bound(x); };
for (auto it = next(lef + 1); it != st.end() && *it < idx; it = next(lef + 1)) {
erase(*it);
}
for (auto it = next(idx + 1); it != st.end() && *it < rig; it = next(idx + 1)) {
erase(*it);
}
erase(idx);
}
for (auto &i : st) {
Remove(i);
}
}
