/* https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest3/device2-review.pdf */
#include "Anna.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int L = 180;
namespace {
long long f(int l) {
return 1LL << (l + 2) / 3;
}
}
int Declare() {
return L;
}
pair<vi, vi> Anna(long long x) {
x--;
int l = 1;
while (x >= f(l))
x -= f(l++);
vi aa(l, 0), bb(l, 0);
for (int i = 0; i < l; i++)
aa[i] = x >> i / 3 & 1, bb[i] = i % 2;
return make_pair(aa, bb);
}
/* https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest3/device2-review.pdf */
#include "Bruno.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int L = 180;
namespace {
long long f(int l) {
return 1LL << (l + 2) / 3;
}
}
int dd[L * 2];
long long Bruno(vi cc) {
int l = cc.size() / 2;
long long x = 1;
for (int l_ = 1; l_ < l; l_++)
x += f(l_);
int k = 0;
for (int i = 0; i < l * 2; i++)
if (cc[i] == 1)
k++;
k -= l / 2;
for (int i = 0, d = 0; i < l * 2; i++)
if (cc[i] == 0)
dd[i] = d++;
else
dd[i] = --d;
vi aa;
int l_ = l, i = 0, d = 0;
while (1) {
if (k == 0) {
while (l_ > 0)
aa.push_back(0), l_--;
break;
}
if (k == l_) {
while (l_ > 0)
aa.push_back(1), l_--;
break;
}
while (1)
if (dd[i] == d * 3 + 2) {
aa.push_back(0), aa.push_back(0), aa.push_back(0);
l_ -= 3, d++;
break;
} else if (dd[i] == d * 3 - 2) {
aa.push_back(1), aa.push_back(1), aa.push_back(1);
k -= 3, l_ -= 3, d--;
break;
} else
i++;
}
for (int i = 0; i < l; i += 3)
if (aa[i])
x += 1LL << i / 3;
return x;
}
