/**
* I'm a bit disappointed. Since only k <= 10 can AC, i think the only solution would
* be to use De Brujin Sequence. k = 10 is already the minimum since it's the
* smallest positive int satisfying 2^k + k - 1 >= n. (I was looking for sth original
* when I started this problem.)
*
* K: log_2(n) (as long as 2^k + k - 1 >= n)
* Implementation 1 (Solves [S1-3], [S5], [S6])
*/
#include <bits/stdc++.h>
#include "squares.h"
typedef std::vector<int> vec;
const int K = 10;
std::vector<vec> graph;
vec path;
void find_path(int k) {
while (!graph[k].empty()) {
int j = graph[k][graph[k].size() - 1];
graph[k].pop_back();
find_path(j);
}
path.push_back(k);
}
vec de_brujin(int k) {
path.clear();
int n = 1 << (k - 1);
graph.assign(n, vec());
for (int i = 0; i < n; i++) {
int j = (i << 1) & ((1 << (k - 1)) - 1);
graph[i].push_back(j);
graph[i].push_back(j | 1);
}
find_path(0);
std::reverse(path.begin(), path.end());
vec seq;
for (int first = path[0]; first > 0; first >>= 1)
seq.push_back(first & 1);
std::reverse(seq.begin(), seq.end());
for (int i = 1; i < int(path.size()); i++)
seq.push_back(path[i] & 1);
return seq;
}
vec seq;
vec paint(int n) {
seq = de_brujin(K);
while (int(seq.size()) > n)
seq.pop_back();
seq.push_back(K);
return seq;
}
int find_location(int n, vec c) {
assert(int(c.size()) == K);
int out_of_bound = 0;
for (int i = K - 1; i >= 0 && c[i] == -1; i--)
out_of_bound++;
if (out_of_bound > 0)
return n - (K - out_of_bound);
for (int start = 0; start + K - 1 < n; start++) {
bool equal = true;
for (int i = 0; i < K && equal; i++)
equal &= (seq[start + i] == c[i]);
if (equal)
return start;
}
return -1; // error
}
