#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);
FOR(i, 0, N){
if(S[i] == 'X'){
firstX = i;
target[i] = 1;
while(i+1 < N && S[i] == S[i+1]) ++i;
FOR(j, i+1, N){
if(S[j] == 'Z') {
target[j] = 1;
while(j+1 < N && S[j] == S[j+1]) ++j;
}
}
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];
}
// cout << sum << '\n';
FOR(i, 0, 61){
Send(sum >> i & 1);
}
}
}
/*
g++ -o grader grader.cpp Anna.cpp Bruno.cpp
#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>;
int count_good_removal(const vc& S, const vi& P){
int N = sz(S);
// FOR(i, 0, N) cout << S[i]; cout << '\n';
// FOR(i, 0, N) cout << P[i] << ' '; cout << '\n';
assert(sz(P) == N);
vi l(N), r(N);
for (int i = 0; i < N; i++) {
l[i] = i - 1;
r[i] = i + 1;
}
int good_count = 0;
for (int i = 0; i < N; i++) {
int d = P[i];
if (l[d] >= 0 && r[d] < N && S[l[d]] == 'X' && S[d] == 'Y' && S[r[d]] == 'Z')
good_count++;
if (l[d] >= 0) r[l[d]] = r[d];
if (r[d] < N) l[r[d]] = l[d];
}
return good_count;
}
int greedy_approach(const vc& S){
int N = sz(S), firstX = -1, lastZ = -1;
FOR(i, 0, N){
if(S[i] == 'X' && firstX == -1) firstX = i;
if(S[i] == 'Z') lastZ = i;
}
if(min(firstX, lastZ) == -1 || firstX > lastZ){
return 0;
}
vi result;
FOR(i, 0, firstX) result.pb(i);
ROF(i, N, lastZ+1) result.pb(i);
int last_removed = firstX;
FOR(i, firstX+1, lastZ+1){
if(S[i] == 'Z'){
ROF(j, i, last_removed+1){
result.pb(j);
}
result.pb(i);
last_removed = i;
}
}
result.pb(firstX);
// for(auto it : result) cout << it << ' '; cout << '\n'; exit(0);
assert(sz(result) == N);
return count_good_removal(S, result);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
// int N;
// cin >> N;
// vc S(N);
// FOR(i, 0, N) {
// char c; cin >> c;
// S[i] = c;
// }
//
// int greedy_solution = greedy_approach(S);
// int brute_solution = 0;
//
// vi perm(N);
// iota(all(perm), 0);
// do{
// maximize(brute_solution, count_good_removal(S, perm));
// } while(next_permutation(all(perm)));
//
// cout << greedy_solution << ' ' << brute_solution << '\n';
//
//
return 0;
}
*/
#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;
}
// FOR(i, 0, L) cout << A[i]; cout << '\n';
// cout << "wtf\n";
assert(sz(A) % 61 == 0);
int nBlocks = sz(A) / 61;
process_fibonacci();
vb target(N);
//leftmost 1 is the first X
//the other 1 is the Z
// cout << sz(A) << '\n';
// cout << dbg(nBlocks) << '\n';
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]) {
// cout << dbg(i - l) << '\n';
sum += 1LL << (i - l);
}
}
// cout << sum << '\n';
assert(sum < fib[T+2]);
ROF(i, T+1, 0){
if(sum >= fib[i]){
// cout << dbg(fib[i]) << '\n';
sum -= fib[i];
// cout << dbg(u + i) << '\n';
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;
}
}
assert(first1 != -1);
FOR(i, 0, first1) result.pb(i);
ROF(i, N, last1+1) result.pb(i);
FOR(i, 1, N){
if(target[i] > 0 && target[i-1]){
return;
}
}
// cout << "Bruno Receive :\n";
// FOR(i, 0, N) cout << target[i] << ' '; cout << '\n';
int last = first1;
// cout << first1 << ' ' << last1 << '\n';
FOR(i, first1+1, last1+1){
if(target[i]){
// cout << dbg(i-1) << dbg(last+1) << '\n';
ROF(j, i, last+1){
// cout << dbg(j) << '\n';
result.pb(j);
}
result.pb(i);
last = i;
}
}
result.pb(first1);
// for(auto it : result) cout << it << ' '; cout << '\n';
// assert(sz(result) == N);
for(auto it : result) Remove(it);
}
// g++ -o grader grader.cpp Anna.cpp Bruno.cpp
