#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#define sz(v) (int)v.size()
#define pb push_back
using bigint = vector<int>; //reversed order
const int base = 2;
bigint operator + (bigint a, bigint b){
int n = max(sz(a), sz(b));
a.resize(n);
b.resize(n);
bigint c(n);
int carry = 0;
for(int i = 0; i < n; ++i){
c[i] = a[i] + b[i] + carry;
if(c[i] >= base){
carry = 1;
c[i] -= base;
} else carry = 0;
}
if(carry) c.pb(carry);
while(!c.empty() && c.back() == 0) c.pop_back();
return c;
}
void show(const bigint& n){
if(n.empty()){
cout << 0 << '\n';
} else{
for(int i = sz(n)-1; i >= 0; --i) cout << n[i];
cout << '\n';
}
}
bool is_greater_or_equal(const bigint& a, const bigint& b){
cout << "comparison :\n";
show(a);
show(b);
cout << '\n';
if(sz(a) != sz(b)) return sz(a) > sz(b);
for(int i = sz(a)-1; i >= 0; --i){
if(a[i] != b[i]) return a[i] > b[i];
}
return true; //equal
}
bigint operator - (bigint a, bigint b){ //assume that a >= b
int n = max(sz(a), sz(b));
a.resize(n); b.resize(n);
int carry = 0;
bigint c(n);
for(int i = 0; i < n; ++i){
c[i] = a[i] - b[i] - carry;
if(c[i] < 0){
c[i] += base;
carry = 1;
} else carry = 0;
}
while(!c.empty() && c.back() == 0) c.pop_back();
return c;
}
}
void Anna(int N, vector<char> S){
int f = -1;
for(int i = 0; i < N; ++i){
if(S[i] == 'X'){
f = i;
break;
}
}
if(f == -1){
Send(0);
return;
}
int nf = f;
while(nf + 1 < N && S[nf+1] == 'Z') ++nf;
vector<bool> bit(N);
bit[f] = true;
for(int i = nf + 1; i < N; ++i){
if(S[i] == 'Z') {
while(i+1 < N && S[i+1] == 'Z') ++i;
bit[i] = true;
}
}
vector<bigint> fib(501);
fib[0] = {1}, fib[1] = {0, 1}, fib[2] = {1, 1};
for(int i = 3; i < sz(fib); ++i){
fib[i] = fib[i-1] + fib[i-2];
}
const int T = 498;
const int B = 348;
// cout << "Anna Send : ";
// for(int i = 0; i < N; ++i) cout << bit[i]; cout << '\n';
for(int l = 0; l < N; l += T){
int r = min(N, l + T);
bigint sum;
for(int i = l; i < r; ++i){
if(bit[i]){
sum = sum + fib[i - l];
}
}
assert(sz(sum) < B);
sum.resize(B);
// show(sum);
for(int i = 0; i < B; ++i){
Send(sum[i]);
}
}
if(nf == f){
for(int i = 0; i < 17; ++i) Send(1);
} else{
for(int i = 0; i < 17; ++i) Send(nf >> i & 1);
}
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
#define sz(v) (int)v.size()
#define pb push_back
#define dbg(x) "[" #x " = " << (x) << "]"
using bigint = vector<short>; //reversed order
const int base = 2;
bigint operator + (bigint a, bigint b){
int n = max(sz(a), sz(b));
a.resize(n);
b.resize(n);
bigint c(n);
int carry = 0;
for(int i = 0; i < n; ++i){
c[i] = a[i] + b[i] + carry;
if(c[i] >= base){
carry = 1;
c[i] -= base;
} else carry = 0;
}
if(carry) c.pb(carry);
while(!c.empty() && c.back() == 0) c.pop_back();
return c;
}
void show(const bigint& n){
if(n.empty()){
cout << 0 << '\n';
} else{
for(int i = sz(n)-1; i >= 0; --i) cout << n[i];
cout << '\n';
}
}
bool is_greater_or_equal(const bigint& a, const bigint& b){
// cout << "comparison :\n";
// show(a);
// show(b);
// cout << '\n';
// cout << sz(a) << ' ' << sz(b) << '\n';
if(sz(a) != sz(b)) return sz(a) > sz(b);
for(int i = sz(a)-1; i >= 0; --i){
// cout << dbg(i) << dbg(a[i]) << dbg(b[i]) << '\n';
if(a[i] != b[i]) {
// cout << dbg(i) << dbg(a[i]) << dbg(b[i]) << '\n';
return a[i] > b[i];
}
}
return true; //equal
}
bigint operator - (bigint a, bigint b){ //assume that a >= b
int n = max(sz(a), sz(b));
a.resize(n); b.resize(n);
int carry = 0;
bigint c(n);
for(int i = 0; i < n; ++i){
c[i] = a[i] - b[i] - carry;
if(c[i] < 0){
c[i] += base;
carry = 1;
} else carry = 0;
}
return c;
}
}
void Bruno(int N, int L, vector<int> A){
if(L == 1){
for(int i = 0; i < N; ++i) Remove(i);
return;
}
vector<bigint> fib(501);
fib[0] = {1}, fib[1] = {0, 1}, fib[2] = {1, 1};
for(int i = 3; i < sz(fib); ++i){
fib[i] = fib[i-1] + fib[i-2];
}
const int T = 498;
const int B = 348;
for(int i = 0; i < sz(fib); ++i) fib[i].resize(B);
int nBlocks = L / B;
vector<bool> bit(N);
for(int b = 0; b < nBlocks; ++b){
int l = b * B, r = (b + 1) * B;
bigint sum;
for(int i = l; i < r; ++i){
sum.pb(A[i]);
}
// show(sum);
for(int i = T; i >= 0; --i){
// show(sum);
// show(fib[i]);
// bool x = is_greater_or_equal(sum, fib[i]);
// cout << dbg(x) << '\n';
if(is_greater_or_equal(sum, fib[i])){
// return;
sum = sum - fib[i];
assert(sz(sum) == B);
bit[i + (b * T)] = 1;
}
}
}
// cout << "Bruno Receive :";
// for(int i = 0; i < N; ++i) cout << bit[i]; cout << '\n';
int extra = 0;
for(int i = 0; i < 17; ++i){
if(A[i + nBlocks * B]) extra |= (1 << i);
}
int f = -1;
for(int i = 0; i < N; ++i){
if(bit[i]){
f = i;
break;
}
}
int s = -1;
for(int i = N - 1; i >= 0; --i){
if(bit[i]){
s = i;
break;
}
}
vector<int> result;
for(int i = 0; i < f; ++i) result.push_back(i);
for(int i = N-1; i > s; --i) result.push_back(i);
int old = -1;
if(extra < N){
old = f;
f = extra;
for(int i = old + 1; i <= f; ++i) result.push_back(i);
}
int last = f;
for(int i = f + 1; i <= s; ++i){
if(bit[i]){
for(int j = i-1; j > last; --j) result.push_back(j);
result.push_back(i);
last = i;
}
}
if(old != -1) result.push_back(old);
else result.push_back(f);
for(int i = 0; i < N; ++i) Remove(result[i]);
}
