#include "squares.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define len(x) (int)(x.size())
template <typename T>
ostream &operator<<(ostream &o, const vector<T> &v)
{
o << "[";
for (int i = 0; i < size(v); i++)
{
o << (i ? "," : "") << v[i];
}
return o << "]";
}
template <typename T1, typename T2>
ostream &operator<<(ostream &o, const map<T1, T2> &v)
{
o << "{\n";
for (auto [e, x] : v)
{
o << " " << e << ": " << x << "\n";
}
return o << "}";
}
const int maxk = 10;
vector<int> gen(int n = maxk)
{
vector<string> twoToNth = {""};
map<string, vector<string>> path;
for (int i = 0; i < n - 1; i++)
{
auto e = move(twoToNth);
for (auto u : e)
{
twoToNth.push_back(u + "1");
twoToNth.push_back(u + "0");
}
}
for (auto t : twoToNth)
{
path[t].push_back((t + "0").substr(1));
// cout << t << " -> " << path[t].back() << "\n";
path[t].push_back((t + "1").substr(1));
// cout << t << " -> " << path[t].back() << "\n";
}
// string pos(n - 1, '1');
string pos(n - 1, '0');
string res = pos;
set<string> visited;
while (true)
{
// cout << pos << " -> ";
char lst = pos[0];
if (!visited.count(pos + "1"))
pos = path[pos][1];
else if (!visited.count(pos + "0"))
pos = path[pos][0];
else
break;
visited.insert(lst + pos);
res.push_back(pos.back());
}
// cout << twoToNth << "\n";
// cout << res << "\n";
vector<int> ress(res.begin(), res.end());
for (auto &r : ress)
r -= '0';
return ress;
}
map<vector<int>, int> prepro(int s)
{
map<vector<int>, int> res;
vector<int> p;
p = gen(s);
for (int i = 0; i < len(p) - s; i++)
{
res[vector<int>(p.begin() + i, p.begin() + i + s)] = i;
}
// cout << res << "\n";
return res;
}
map<vector<int>, int> indexes = prepro(maxk);
std::vector<int> paint(int n)
{
std::vector<int> labels = gen(maxk);
labels.resize(n);
labels.push_back(maxk);
// cout << labels << "\n";
return labels;
}
int find_location(int n, std::vector<int> c)
{
int minuspos = find(c.begin(), c.end(), -1) - c.begin();
// cout << c << "\n";
// cout << minuspos << " minuspos\n";
if(minuspos < len(c))
{
return n - minuspos;
}
return indexes[c];
}
