#include <bits/stdc++.h>
#include "squares.h"
using namespace std;
bool graph_made = false;
array<int, 1024> graph;
array<int, 1024> node_to_cycle;
vector<set<int>> cycles;
array<bool, 1024> visited;
array<int, 1024> node_to_pos;
void make_graph()
{
graph_made = true;
for (int i = 512; i < 1024; i++) graph[i] = 1;
int cycle_count = 0;
for (int i = 0; i < 1024; i++)
{
if (visited[i]) continue;
set<int> cycle;
for (int node = i; !visited[node]; node = (node << 1) & 1023 | graph[node])
{
visited[node] = true;
cycle.insert(node);
node_to_cycle[node] = cycle_count;
}
cycles.push_back(cycle);
cycle_count++;
}
for (int i = 0; i < 1024; i++)
{
if (node_to_cycle[i] != node_to_cycle[i ^ 512])
{
graph[i] ^= 1;
graph[i ^ 512] ^= 1;
int new_cycle = node_to_cycle[i];
int old_cycle = node_to_cycle[i ^ 512];
for (int node : cycles[old_cycle])
{
cycles[new_cycle].insert(node);
node_to_cycle[node] = new_cycle;
}
}
}
int pos = 0;
for (int node = 0; pos < 1024; pos++)
{
node_to_pos[node] = pos;
node = (node << 1) & 1023 | graph[node];
}
}
vector<int> paint(int n)
{
if (!graph_made) make_graph();
vector<int> answer(n + 1);
int pos = 0;
for (; pos < 10 && pos < n; pos++) answer[pos] = 0;
for (int node = 0; pos < n; pos++)
{
answer[pos] = graph[node];
node = (node << 1) & 1023 | graph[node];
}
answer[n] = 10;
return answer;
}
int find_location(int n, vector<int> c)
{
if (!graph_made) make_graph();
for (int i = 0; i < 10; i++)
{
if (c[i] == -1) return n - i;
}
int node = 0;
for (int i = 0; i < 10; i++) node += c[i] * (1 << (9 - i));
return node_to_pos[node];
}
