#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>

std::vector<std::vector<int>> a;
std::vector<int> result;
constexpr size_t LENGTH = 1024;

void calculate(int l, int r, int dep) {
  if (l > r)
    return;
  int mid = (l + r) >> 1;
  a[dep].push_back(mid + 1);
  calculate(l, mid - 1, dep + 1);
  calculate(mid + 1, r, dep + 1);
}

size_t calculate_location(size_t index) {
  int step = (int)std::log2(++index) + 1;
  auto location =
      LENGTH / (1 << step) * ((index & ((1 << (step - 1)) - 1)) * 2 + 1);
  return location ? location : LENGTH;
}
typedef int key_type;

int get_son_from_step(int point, bool negative) {
  return negative ? point * 2 : point * 2 + 1;
}

const key_type *cudaBinarySearch(key_type *const start, const key_type *end,
                                 const key_type val) {
  int step_limit = (int)std::log2(LENGTH) + 1;
  key_type *last_known_point = start;
  auto son = 0;

  for (int i = 0; i < step_limit; i++) {
    const auto next_level_start = start + (1 << (i + 1)) - 1;
    if (*last_known_point == val) {
      return last_known_point;
    }
    son = get_son_from_step(son, (*last_known_point > val));
    last_known_point = next_level_start + son;
    printf("%d\n", *last_known_point);
  }
  return last_known_point;
}

int main() {
  int n = LENGTH;

  int c = 0;
  for (int k = n; k; k >>= 1)
    c++;
  a.resize(c);
  calculate(0, n - 1, 0);
  for (auto &i : a) {
    for (int &j : i) {
      // cout << j << ' ';
      result.push_back(j);
    }
  }

  for (int i = 0; i < 32; i++) {
    printf("%3d ", i);
  }

  puts("");

  for (int i = 0; i < 32; i++) {
    printf("%3d ", result[i]);
    assert(calculate_location(i) == result[i]);
  }
  puts("");
  cudaBinarySearch(&result[0], &*result.end(), 1024);
  return 0;
}