/* https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest3/device2-review.pdf */
#include "Anna.h"
#include <vector>
using namespace std;
const int L = 2000;
typedef vector<int> vi;
namespace {
long long f(int l) {
return (long long) (l / 3 + 1) * ((l + 1) / 3 + 1) * ((l + 2) / 3 * 2 + 1);
}
}
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);
int l0 = l / 3, l1 = (l + 1) / 3, l2 = (l + 2) / 3;
int kl = x % (l0 + 1), kr = x / (l0 + 1) % (l1 + 1), km = x / (l0 + 1) / (l1 + 1);
for (int i = 0; i < kl; i++)
aa[i] = bb[l0 - 1 - i] = 1;
for (int i = l - 1; i >= l - kr; i--)
aa[i] = bb[l - l1 + l - 1 - i] = 1;
if (km <= l2)
for (int i = 0; i < km; i++)
aa[l0 + i] = 1;
else {
for (int i = 0; i < l2; i++)
aa[l0 + i] = 1;
for (int i = 0; i < km - l2; i++)
bb[l0 + i] = 1;
}
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;
namespace {
long long f(int l) {
return (long long) (l / 3 + 1) * ((l + 1) / 3 + 1) * ((l + 2) / 3 * 2 + 1);
}
}
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 l0 = l / 3;
int l1 = (l + 1) / 3;
int kl = 0;
for (int i = 0; i < l0; i++)
if (cc[i] == 1)
kl++;
int kr = 0;
for (int i = l * 2 - 1; i >= l * 2 - l1; i--)
if (cc[i] == 1)
kr++;
int km = 0;
for (int i = 0; i < l * 2; i++)
if (cc[i] == 1)
km++;
km -= (kl + kr) * 2;
return x + ((long long) km * (l1 + 1) + kr) * (l0 + 1) + kl;
}
