#include "squares.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> paint(int n) {
vector<int> labels(n+1);
int a = min(n, 10);
labels[n] = a;
for (int i = 0; i < a; i++) labels[i] = 0;
int cur = 0;
int idx = a;
vector<bool> seen((1<<a)+1);
while (idx < n) {
seen[cur] = true;
int x = cur-(labels[idx-a] << (a-1));
x = (x << 1);
if (!seen[x+1]) {
labels[idx] = 1;
cur = x+1;
}
else if (!seen[x]) {
labels[idx] = 0;
cur = x;
}
else break;
idx++;
}
return labels;
}
int find_location(int n, vector<int> c) {
vector<int> labels(n+c.size()+1, -1);
int a = min(n, 10);
for (int i = 0; i < a; i++) labels[i] = 0;
int cur = 0;
int idx = a;
vector<bool> seen((1<<a)+1);
while (idx < n) {
seen[cur] = true;
int x = cur-(labels[idx-a] << (a-1));
x = (x << 1);
if (!seen[x+1]) {
labels[idx] = 1;
cur = x+1;
}
else if (!seen[x]) {
labels[idx] = 0;
cur = x;
}
else break;
idx++;
}
for (int i = 0; i < n; i++) {
int idx = i;
bool poss = true;
for (int j = 0; j < c.size(); j++, idx++) {
if (labels[idx] != c[j]) {
poss = false;
break;
}
}
if (poss) return i;
}
return -1;
}
