/* 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 {
int f(int l) {
if (l == 1)
return 3;
if (l == 2)
return 6;
return (l * 2 - 3) * 4;
}
int g(int l, int k) {
int n = 0;
if (k >= 4)
n++;
if (l * 2 - k >= 4)
n++;
if (k >= 2 && l * 2 - k >= 2)
n += 2;
if (n == 0)
n = 1;
return n;
}
}
int Declare() {
return L;
}
pair<vi, vi> Anna(long long x) {
x--;
int l = 1;
while (x >= f(l))
x -= f(l++);
int k = 0;
while (x >= g(l, k))
x -= g(l, k++);
vi aa(l, 0), bb(l, 0);
if (k >= 4 && x-- == 0) {
aa[0] = bb[0] = 1;
aa[l - 1] = bb[l - 1] = 1;
if (k <= l + 2)
for (int i = 1; i <= k - 4; i++)
aa[i] = 1;
else {
for (int i = 1; i <= l - 2; i++)
aa[i] = 1;
for (int i = 1; i <= k - l - 2; i++)
bb[i] = 1;
}
} else if (l * 2 - k >= 4 && x-- == 0) {
aa[0] = bb[0] = 0;
aa[l - 1] = bb[l - 1] = 0;
if (k <= l - 2)
for (int i = 1; i <= k; i++)
aa[i] = 1;
else {
for (int i = 1; i <= l - 2; i++)
aa[i] = 1;
for (int i = 1; i <= k - l + 2; i++)
bb[i] = 1;
}
} else if (k >= 2 && l * 2 - k >= 2 && x-- == 0) {
aa[0] = bb[0] = 0;
aa[l - 1] = bb[l - 1] = 1;
if (k <= l)
for (int i = 1; i <= k - 2; i++)
aa[i] = 1;
else {
for (int i = 1; i <= l - 2; i++)
aa[i] = 1;
for (int i = 1; i <= k - l; i++)
bb[i] = 1;
}
} else if (k >= 2 && l * 2 - k >= 2 && x-- == 0) {
aa[0] = bb[0] = 1;
aa[l - 1] = bb[l - 1] = 0;
if (k <= l)
for (int i = 1; i <= k - 2; i++)
aa[i] = 1;
else {
for (int i = 1; i <= l - 2; i++)
aa[i] = 1;
for (int i = 1; i <= k - l; i++)
bb[i] = 1;
}
} else {
if (k <= l)
for (int i = 0; i < k; i++)
aa[i] = 1;
else {
for (int i = 0; i < l; i++)
aa[i] = 1;
for (int i = 0; i < k - l; i++)
bb[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 {
int f(int l) {
if (l == 1)
return 3;
if (l == 2)
return 6;
return (l * 2 - 3) * 4;
}
int g(int l, int k) {
int n = 0;
if (k >= 4)
n++;
if (l * 2 - k >= 4)
n++;
if (k >= 2 && l * 2 - k >= 2)
n += 2;
if (n == 0)
n = 1;
return n;
}
}
long long Bruno(vi cc) {
int l = cc.size() / 2, k = 0;
for (int i = 0; i < l * 2; i++)
if (cc[i] == 1)
k++;
int x = 1;
for (int l_ = 1; l_ < l; l_++)
x += f(l_);
for (int k_ = 0; k_ < k; k_++)
x += g(l, k_);
if (g(l, k) > 1) {
if (cc[0] == 1 && cc[l * 2 - 1] == 1)
return x;
if (k >= 4)
x++;
if (cc[0] == 0 && cc[l * 2 - 1] == 0)
return x;
if (l * 2 - k >= 4)
x++;
if (cc[0] == 0 && cc[l * 2 - 1] == 1)
return x;
if (k >= 2 && l * 2 - k >= 2)
x++;
}
return x;
}
