#include "squares.h"
#include <bits/stdc++.h>
using namespace std;
const int LM=1234, m=1<<9;
vector<int> G[LM], ep;
void dfs(int x){
while(!G[x].empty()){
int t=G[x].back();
G[x].pop_back();
dfs(t);
}
ep.push_back(x);
}
int D[LM];
vector<int> paint(int n){
vector<int>ret;
for(int i=0; i<m; i++){
G[i].push_back((i<<1)%m);
G[i].push_back(((i<<1)+1)%m);
}
ep.clear();
fill(D,D+(1<<10),0);
dfs(0);
reverse(ep.begin(),ep.end());
ret.assign(min(9,n), 0);
for(int i=1; i<n-8; i++) ret.push_back(ep[i]%2);
for(int i=0; i<n-10; i++){
int t=0;
for(int j=0; j<10; j++) t += ret[i+j]<<j;
D[t]=i;
}
ret.push_back(min(10,n));
return ret;
}
int find_location(int n, vector<int>c){
if(c.back()==-1 || n<10){
int k=0;
for(int i:c) k+=i<0;
return max(n-10, 0)+k;
}
int t=0;
for(int i=0; i<10; i++) t+=c[i]<<i;
return D[t];
}
