// william-ac
#include "squares.h"
#include <vector>
std::vector<int> labels, visited, euler_path;
int reverse_map[1024];
void dfs(int x) {
while (visited[x] < 2) {
dfs((x >> 1) | (visited[x]++ << 8));
}
euler_path.push_back(x);
}
void generate_map() {
visited.assign(512, 0);
euler_path.clear();
dfs(0);
labels.clear();
labels.assign(8, 0);
for (int i = 0; i < (int)euler_path.size() - 1; i++) {
labels.push_back(euler_path[i] & 1);
reverse_map[(euler_path[i] << 1) | (euler_path[i + 1] & 1)] = i;
}
}
std::vector<int> paint(int n) {
if (euler_path.empty()) {
generate_map();
}
std::vector<int> painting(n + 1);
for (int i = 0; i < n; i++) {
painting[i] = labels[i];
}
painting[n] = 10;
return painting;
}
int find_location(int n, std::vector<int> c) {
if (euler_path.empty()) {
generate_map();
}
int val = 0;
for (int i = 0; i < (int)c.size(); i++) {
if (c[i] == -1) return n - i;
val = (val << 1) | c[i];
}
return reverse_map[val];
}
