#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;
namespace {
const int MAX = 100;
const int T = 90;
ll fib[MAX];
void process_fibonacci(){ //
fib[0] = 1; fib[1] = 2; fib[2] = 3;
FOR(i, 3, MAX) fib[i] = fib[i-2] + fib[i-1];
}
int find_compression_length(){ //[fib[T+2] = 1293530146158671551][T = 90][bits = 61][cost = 67832]
vl fib(91);
fib[0] = 1; fib[1] = 2;
fib[2] = 3;
FOR(i, 3, 91) fib[i] = fib[i-2] + fib[i-1];
int N = 1e5;
for(int T = 2; T <= N; ++T){
int nT = (N + T - 1) / T;
int bits = 32 - __builtin_clz(fib[T+2]);
int cost = nT * bits;
if(cost <= 70000){
cout << dbg(T) << dbg(bits) << dbg(cost) << '\n';
return T;
}
}
return -1;
}
}
void Anna(int N, std::vector<char> S) {
int firstX = -1;
vb target(N, false);
int special_case = -1;
FOR(i, 0, N){
if(S[i] == 'X'){
firstX = i;
target[i] = 1;
while(i+1 < N && S[i+1] == 'Z') ++i;
if(i != firstX) special_case = i;
FOR(j, i+1, N){
if(S[j] == 'Z') {
while(j+1 < N && S[j] == S[j+1]) ++j;
target[j] = 1;
}
}
break;
}
}
if(firstX == -1){
Send(0);
return;
}
//cout << "Anna Send : \n";
//FOR(i, 0, N) cout << target[i] << ' '; cout << '\n';
process_fibonacci();
for(int l = 0; l < N; l += T){ //T = 44
int r = min(N-1, l + T-1);
ll sum = 0;
FOR(i, l, r+1){
if(target[i]) sum += fib[i - l];
}
FOR(i, 0, 61){
Send(sum >> i & 1);
}
}
if(special_case == -1){
FOR(i, 0, 17) Send(1);
} else{
FOR(i, 0, 17) Send(special_case >> i & 1);
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true;
return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true;
return false;
}
using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;
namespace {
const int MAX = 100;
const int T = 90;
ll fib[MAX];
void process_fibonacci(){ //
fib[0] = 1; fib[1] = 2; fib[2] = 3;
FOR(i, 3, MAX) fib[i] = fib[i-2] + fib[i-1];
}
int find_compression_length(){ //[fib[T+2] = 1293530146158671551][T = 90][bits = 61][cost = 67832]
vl fib(91);
fib[0] = 1; fib[1] = 2;
fib[2] = 3;
FOR(i, 3, 91) fib[i] = fib[i-2] + fib[i-1];
int N = 1e5;
for(int T = 2; T <= N; ++T){
int nT = (N + T - 1) / T;
int bits = 32 - __builtin_clz(fib[T+2]);
int cost = nT * bits;
if(cost <= 70000){
cout << dbg(T) << dbg(bits) << dbg(cost) << '\n';
return T;
}
}
return -1;
}
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void Bruno(int N, int L, std::vector<int> A) {
if(sz(A) == 1){
vi perm(N);
iota(all(perm), 0);
shuffle(all(perm), rng);
for(auto it : perm) Remove(it);
return;
}
// assert(sz(A) % 61 == 0); because of special case
int nBlocks = sz(A) / 61;
int special_case = 0;
FOR(i, 0, 17){
if(A[i + nBlocks * 61]) special_case |= (1 << i);
}
process_fibonacci();
vb target(N);
if(special_case < N) target[special_case] = 1;
//leftmost 1 is the first X
//the other 1 is the Z
FOR(i, 0, nBlocks){
int l = i * 61, r = (i + 1) * 61;
int u = i * 90, v = (i + 1) * 90;
ll sum = 0;
FOR(i, l, r){
if(A[i]) {
sum += 1LL << (i - l);
}
}
ROF(i, T+1, 0){
if(sum >= fib[i]){
sum -= fib[i];
target[u + i] = true;
}
}
}
vi result;
int first1 = -1, last1 = -1;
FOR(i, 0, N){
if(target[i]){
first1 = i;
break;
}
}
ROF(i, N, 0){
if(target[i]){
last1 = i;
break;
}
}
FOR(i, 0, first1) result.pb(i);
ROF(i, N, last1+1) result.pb(i);
int last = first1;
FOR(i, first1+1, last1+1){
if(target[i]){
ROF(j, i, last+1){
result.pb(j);
}
result.pb(i);
last = i;
}
}
result.pb(first1);
for(auto it : result) {
Remove(it);
}
}
// g++ -o grader grader.cpp Anna.cpp Bruno.cpp
