#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
// We use a global or static vector to store the sequence so both
// functions can access the same "ruler."
vector<int> de_bruijn;
bool visited[1025][2];
void build_de_bruijn(int u, int k_val) {
for (int bit = 0; bit < 2; ++bit) {
if (!visited[u][bit]) {
visited[u][bit] = true;
// Standard De Bruijn construction: move to next state
// Next state is (current_state << 1 | bit) & mask
build_de_bruijn(((u << 1) | bit) & ((1 << (k_val - 1)) - 1), k_val);
de_bruijn.push_back(bit);
}
}
}
// Phase 1: Painting the squares
// n: number of squares, return: {colors, k}
pair<vector<int>, int> paint(int n) {
int k = 10;
de_bruijn.clear();
for(int i=0; i<1025; ++i) visited[i][0] = visited[i][1] = false;
build_de_bruijn(0, k);
// The sequence needs to be padded slightly to handle windows at the end
vector<int> result;
for (int i = 0; i < n; ++i) {
result.push_back(de_bruijn[i]);
}
return {result, k};
}
// Phase 2: Finding the location
// n: total squares, window: the k colors seen
int find_location(int n, vector<int> window) {
int k = window.size();
// Regenerate the same sequence used in paint()
de_bruijn.clear();
for(int i=0; i<1025; ++i) visited[i][0] = visited[i][1] = false;
build_de_bruijn(0, 10); // k is 10 for N=1000
// Slide through the sequence to find where the window matches
for (int i = 0; i <= n - k; ++i) {
bool match = true;
for (int j = 0; j < k; ++j) {
if (de_bruijn[i + j] != window[j]) {
match = false;
break;
}
}
if (match) return i;
}
return -1; // Should not reach here if logic is correct
}
