#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
/**
* A helper function to build the unique sequence of colors.
* This is the "ruler" that both the painter and the finder use.
*/
vector<int> build_ruler(int n, int k) {
int num_states = 1 << k; // 2^k, which is 1024 for k=10
vector<int> path;
vector<bool> visited(num_states, false);
// Simple DFS to find a path through the bit-patterns
// u is our current k-bit number (state)
int current_node = 0;
for (int i = 0; i < num_states; ++i) {
visited[current_node] = true;
path.push_back(current_node);
// Try to move to the next state by shifting bits
// Next state is either (current << 1) or (current << 1 + 1)
int next_with_zero = (current_node * 2) % num_states;
int next_with_one = (current_node * 2 + 1) % num_states;
if (!visited[next_with_one]) {
current_node = next_with_one;
} else if (!visited[next_with_zero]) {
current_node = next_with_zero;
} else {
break; // No more unique states to visit
}
}
// Convert the path of numbers into a sequence of individual 0/1 colors
vector<int> ruler;
// 1. Add all bits of the very first number
for (int i = k - 1; i >= 0; --i) {
int bit = (path[0] >> i) & 1;
ruler.push_back(bit);
}
// 2. For every following number, just add its last (newest) bit
for (int i = 1; i < (int)path.size() && (int)ruler.size() < n; ++i) {
ruler.push_back(path[i] & 1);
}
return ruler;
}
/**
* PHASE 1: The Painter
*/
vector<int> paint(int n) {
int k = min(10, n);
vector<int> colors = build_ruler(n, k);
// The grader expects size n+1, with K at the very end
colors.resize(n + 1);
colors[n] = k;
return colors;
}
/**
* PHASE 2: The Finder
*/
int find_location(int n, vector<int> reported_window) {
int k = reported_window.size();
vector<int> full_ruler = build_ruler(n, k);
// Slide through the ruler to find where the window matches
for (int i = 0; i < n; i++) {
bool match = true;
for (int j = 0; j < k; j++) {
int expected_color = (i + j >= n) ? -1 : full_ruler[i + j];
if (expected_color != reported_window[j]) {
match = false;
break;
}
}
if (match) return i;
}
return -1; // Should never happen
}
