#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
// base 2^60
class bigint {
vector<int64_t> a; // little endian. x = a[0] * (2^60)^0 + a[1] * (2^60)*1 + ...
public:
bigint() : a(1) {}
bigint(int x) : a(1) {
a[0] = x;
}
bigint(string s) { // assumes len % 60 == 0
a.resize(s.length() / 60);
for (int i = 0; i < a.size(); ++i) {
a[i] = stoll(s.substr(60 * i, 60), nullptr, 2);
}
}
bigint &operator+=(const bigint &r) {
a.resize(max(a.size(), r.a.size()) + 1);
for (int i = 0; i < a.size() - 1; ++i) {
a[i] += i < r.a.size() ? r.a[i] : 0;
a[i + 1] += a[i] >> 60;
a[i] %= 1ll << 60;
}
while (!a.empty() && a.back() == 0) {
a.pop_back();
}
if (a.empty()) {
a.push_back(0);
}
return *this;
}
bigint operator+(const bigint &r) const { return bigint{*this} += r; }
bigint operator-=(const bigint &r) { // assumes a.size() >= r.a.size()
a.push_back(0);
for (int i = 0; i < r.a.size(); ++i) {
a[i] -= r.a[i];
if (a[i] < 0) {
a[i] += 1ll << 60;
a[i + 1]--;
}
}
while (!a.empty() && a.back() == 0) {
a.pop_back();
}
if (a.empty()) {
a.push_back(0);
}
return *this;
}
bigint operator-(const bigint &r) const { return bigint{*this} -= r; }
bool operator<(const bigint &r) const {
if (a.size() < r.a.size()) {
return true;
}
bigint res = *this - r;
return res.a.back() < 0;
};
bool operator>=(const bigint &r) const { return !(*this < r); }
string to_string() const {
string ans;
for (const int64_t &i : a) {
ans += bitset<60>{uint64_t(i)}.to_string();
}
return ans;
}
};
string encode(string s) {
reverse(s.begin(), s.end());
const int n = s.length();
vector<bigint> dp(n + 1);
dp[0] = 1, dp[1] = 2;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
bigint res = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
res += dp[i];
}
}
return res.to_string();
}
} // namespace
void Anna(int N, std::vector<char> S) {
int xloc = -1, zloc = -1;
for (int i = N - 1; i >= 0; --i) {
if (S[i] == 'X') {
xloc = i;
}
}
for (int i = 0; i < N; ++i) {
if (S[i] == 'Z') {
zloc = i;
}
}
if (xloc == -1 || zloc == -1 || xloc > zloc) {
return;
}
string s;
for (int i = 0; i < N; ++i) {
s.push_back(xloc <= i && i <= zloc && (i == xloc || (S[i] == 'Z' && i - 1 != xloc && i + 1 != N && S[i + 1] != 'Z')) ? '1' : '0');
}
for (char &c : encode(s)) {
Send(c == '1');
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
// base 2^60
class bigint {
vector<int64_t> a; // little endian. x = a[0] * (2^60)^0 + a[1] * (2^60)*1 + ...
public:
bigint() : a(1) {}
bigint(int x) : a(1) {
a[0] = x;
}
bigint(string s) { // assumes len % 60 == 0
a.resize(s.length() / 60);
for (int i = 0; i < a.size(); ++i) {
a[i] = stoll(s.substr(60 * i, 60), nullptr, 2);
}
}
bigint &operator+=(const bigint &r) {
a.resize(max(a.size(), r.a.size()) + 1);
for (int i = 0; i < a.size() - 1; ++i) {
a[i] += i < r.a.size() ? r.a[i] : 0;
a[i + 1] += a[i] >> 60;
a[i] %= 1ll << 60;
}
while (!a.empty() && a.back() == 0) {
a.pop_back();
}
if (a.empty()) {
a.push_back(0);
}
return *this;
}
bigint operator+(const bigint &r) const { return bigint{*this} += r; }
bigint operator-=(const bigint &r) { // assumes a.size() >= r.a.size()
a.push_back(0);
for (int i = 0; i < r.a.size(); ++i) {
a[i] -= r.a[i];
if (a[i] < 0) {
a[i] += 1ll << 60;
a[i + 1]--;
}
}
while (!a.empty() && a.back() == 0) {
a.pop_back();
}
if (a.empty()) {
a.push_back(0);
}
return *this;
}
bigint operator-(const bigint &r) const { return bigint{*this} -= r; }
bool operator<(const bigint &r) const {
if (a.size() < r.a.size()) {
return true;
}
bigint res = *this - r;
return res.a.back() < 0;
};
bool operator>=(const bigint &r) const { return !(*this < r); }
string to_string() const {
string ans;
for (const int64_t &i : a) {
ans += bitset<60>{uint64_t(i)}.to_string();
}
return ans;
}
};
string decode(string s, int n) {
vector<bigint> dp(n + 1);
dp[0] = 1, dp[1] = 2;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
bigint res(s);
string ans(n, '0');
for (int i = n - 1; i >= 0; --i) {
if (res >= dp[i]) {
res -= dp[i];
ans[i] = '1';
}
}
reverse(ans.begin(), ans.end());
return ans;
}
} // namespace
void Bruno(int N, int L, std::vector<int> A) {
auto rem_all = [&]() { for (int i = 0; i < N; ++i) { Remove(i); } };
if (L == 0) {
return rem_all();
}
string enc;
for (int i = 0; i < L; ++i) {
enc.push_back(A[i] ? '1' : '0');
}
string s = decode(enc, N);
if (count(s.begin(), s.end(), '1') == 1) {
return rem_all();
}
int xloc = -1, zloc = -1;
for (xloc = 0; xloc < N && s[xloc] != '1'; ++xloc) {
Remove(xloc);
}
for (zloc = N - 1; zloc >= 0 && s[zloc] != '1'; --zloc) {
Remove(zloc);
}
for (int i = xloc + 1, l = xloc + 1; i <= zloc; ++i) {
if (s[i] != '1') {
continue;
}
for (int j = i - 1; j >= l; --j) {
Remove(j);
}
Remove(i);
l = i + 1;
}
Remove(xloc);
}
