#include "squares.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> get (int k) {
if (k == 1) {
return {0, 1};
}
k--;
set <int> adj[1 << k];
auto add_edge = [&] (int x, int y) -> void {
adj[x].insert(y);
};
for (int i = 0; i < (1 << k); i++) {
add_edge(i / 2, i);
add_edge((i / 2) + (1 << (k - 1)), i);
}
vector <int> ans;
stack <int> cur;
cur.push(0);
while (!cur.empty()) {
auto k = cur.top();
if (adj[k].empty()) {
ans.push_back(k);
cur.pop();
} else {
auto v = *(--adj[k].end());
adj[k].erase(v);
cur.push(v);
}
}
reverse(ans.begin(), ans.end());
vector <int> ret;
for (int i = 0; i - 1 < k; i++) {
ret.push_back(0);
}
for (int i = 1; i < (int)ans.size(); i++) {
ret.push_back(ans[i] & 1);
}
ret.pop_back();
return ret;
}
std::vector<int> paint (int n) {
int k = 1;
while ((1 << k) + k - 1 < n) {
k++;
}
auto g = get(k);
while (g.size() > n) g.pop_back();
g.push_back(k);
return g;
}
int find_location(int n, std::vector<int> c) {
if (c.back() == -1) {
int cnt = 0;
for (auto i : c) {
cnt += i == -1;
}
return n - ((int)c.size() - cnt);
}
int k = 1;
while ((1 << k) + k - 1 < n) {
k++;
}
auto g = get(k);
for (int i = 0; i < n; i++) {
int flag = 1;
for (int j = 0; j < k; j++) {
flag &= g[i + j] == c[j];
}
if (flag) {
return i;
}
}
assert(0);
return 0;
}
