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

typedef unsigned long long key_type;
std::vector<unsigned long long> population_vector, sample_vector;
std::vector<bool> result_storage;
constexpr size_t SAMPLE_LENGTH = 1024, TEST_LENGTH = 1024;

constexpr int MOVE_OFFSET = sizeof(key_type) * 8 - 1;
constexpr size_t MAX_SCALE = 3;

size_t fast_log(size_t a) {
  float t = a;
  return (((*(int *)&t) >> 23) + 1) & 127;
}
// calculate location by number
size_t calculate_location(size_t index) {
  size_t bit_low = SAMPLE_LENGTH >> fast_log(++index) >> 1;
  return (!bit_low) ? SAMPLE_LENGTH
                    : ((index << 1) | 1) * bit_low - SAMPLE_LENGTH;
}

// calculate number by location
size_t calculate_location_inverse(size_t index) {
  ++index;
  size_t low_bit = index & (-index);
  return (low_bit == SAMPLE_LENGTH) ? SAMPLE_LENGTH
                                    : ((SAMPLE_LENGTH + index) / low_bit) >> 1;
}

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

const key_type *cudaBinarySearch(key_type *const start, const key_type val) {
  int step_limit = (int)fast_log(SAMPLE_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));
    son = son * 2 + (int)((*last_known_point - val) >> MOVE_OFFSET);
    // if (son < 0) son = 0;
    /*printf("%d %d %d\n", (1 << (i + 1)), son,
           -(int)((*last_known_point - val) >> MOVE_OFFSET));*/
    last_known_point = next_level_start + son;
  }
  return last_known_point;
}

long double sample_cdf(long double x) {
  auto it = std::lower_bound(sample_vector.begin(), sample_vector.end(), x);
  if (it == sample_vector.end()) {
    return 1;
  }
  if (it == sample_vector.begin()) {
    return 0;
  }
  auto it_prev = it - 1;

  return ((long double)(it_prev - sample_vector.begin()) +
          (long double)(x - *it_prev) / (*it - *it_prev)) /
         (long double)(sample_vector.size() - 1);
}

long double sample_cdf_custom_version(long double x) {
  auto it = cudaBinarySearch(sample_vector.data(), x);
  assert(it < &*sample_vector.end());
  assert(it >= sample_vector.data());
  if (it == (&*sample_vector.end() - 1)) {
    return 1;
  }
  if (it == sample_vector.data()) {
    return 0;
  }

  auto prev_real_location =
      calculate_location_inverse(it - sample_vector.data()) - 2;

  auto it_prev =
      sample_vector.data() + calculate_location(prev_real_location) - 1;

  auto test = ((long double)prev_real_location +
               (long double)(x - *it_prev) / (*it - *it_prev)) /
              (long double)(SAMPLE_LENGTH - 1);
  return test;
}

unsigned long long max_value = 0, min_value = 0xfffffffff;
inline void store_into_vector(unsigned long long value) {
  if (max_value < value) {
    max_value = value;
  }
  if (min_value > value) {
    min_value = value;
  }
  population_vector.push_back(value);
}

inline long double safe_ceil(long double value) {
  auto c = std::ceil(value);
  return c == 0 ? 1 : c;
}

typedef long double (*cdf_function_type)(long double);
typedef void (*init_function_type)(const std::vector<key_type> &);

void process_function(const std::vector<key_type> &tmp,
                      cdf_function_type cdf_function, init_function_type init) {
  sample_vector.clear();
  sample_vector.resize(SAMPLE_LENGTH);

  init(tmp);

  for (size_t scale = 2; scale < MAX_SCALE; scale++) {
    const long split_size = TEST_LENGTH * scale;
    result_storage.clear();
    result_storage.resize(scale * SAMPLE_LENGTH, false);
    auto slice_size = 1.0 / (double)(split_size);

    // printf("\nscale: %d\n", scale);
    for (size_t i = 0; i < TEST_LENGTH; i++) {

      auto index =
          (int)safe_ceil(cdf_function(population_vector[i + SAMPLE_LENGTH]) /
                         slice_size) -
          1;
      // printf("index: %d\n", index);
      while (result_storage[index]) {
        index++;
      }
      result_storage[index] = true;
    }
    for (auto &&element : result_storage) {
      printf("%d", element ? 1 : 0);
    }
    puts("");
  }
}

void process_function(const std::vector<key_type> &tmp,
                      cdf_function_type cdf_function) {
  process_function(tmp, cdf_function, [](const std::vector<key_type> &tmp) {
    sample_vector.assign(tmp.begin(), tmp.end());
  });
}

int main() {
  FILE *file = fopen("normal_distribution.txt", "r");
  assert(file);
  for (long long i; fscanf(file, "%lld ", &i) != EOF; store_into_vector(i))
    ;
  fclose(file);

  std::vector<key_type> tmp(population_vector.begin(),
                            population_vector.begin() + SAMPLE_LENGTH - 2);
  tmp.push_back(max_value);
  tmp.push_back(min_value);
  std::sort(tmp.begin(), tmp.end());

  process_function(tmp, sample_cdf);
  process_function(
      tmp, sample_cdf_custom_version, [](const std::vector<key_type> &tmp_) {
        for (size_t i = 0; i < SAMPLE_LENGTH; i++) {
          sample_vector[calculate_location_inverse(i) - 1] = tmp_[i];
          auto location = calculate_location(i);
          auto location2 = calculate_location_inverse(location - 1);
          assert(location2 - 1 == i);
          // printf("%zu %zu\n", location, location2);
        }
      });
  // valid_sort(tmp);
}