// Experimental content: test scale for element cell
/*
Sample output:
scale:  2, max: 7  2: 339 3:  86 4:  27 5:  13 6:   2 7:   2
scale:  3, max: 6  2: 287 3:  70 4:  18 5:   2 6:   1
scale:  4, max: 5  2: 257 3:  43 4:  14 5:   3
scale:  5, max: 5  2: 241 3:  46 4:   6 5:   1
scale:  6, max: 4  2: 226 3:  26 4:   3
scale:  7, max: 4  2: 188 3:  26 4:   1
scale:  8, max: 4  2: 182 3:  20 4:   3
scale:  9, max: 4  2: 165 3:  17 4:   3
scale: 10, max: 4  2: 154 3:  16 4:   1
scale: 11, max: 4  2: 153 3:   9 4:   1
scale: 12, max: 4  2: 127 3:  11 4:   1
scale: 13, max: 3  2: 135 3:   5
scale: 14, max: 3  2: 118 3:   7
scale: 15, max: 3  2: 129 3:   4
scale: 16, max: 4  2: 108 3:   5 4:   1
 */
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

constexpr size_t length = 2097152;
std::vector<unsigned long long> population_vector, sample_vector,
    original_vector;
// std::vector<std::vector<unsigned long long>> result_storage;
std::vector<short> result_storage;
std::vector<short> counter;

long double sample_cdf(long double x) {
  auto it = 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);
}

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

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);
}

constexpr long sample_length = 1024;
constexpr long test_size = 2048;

void mian(long scale_size) {
  const long split_size = test_size * scale_size;
  counter.resize(8);

  result_storage.resize(split_size, 0);

  const auto slice_size = 1.0 / (long double)(split_size);

  for (long i = 0; i < test_size; i++) {
    auto index =
        safe_ceil(sample_cdf(original_vector[i + sample_length]) / slice_size) -
        1;
    // printf("%Lf\n", index);
    result_storage[(int)index]++;
  }
  auto element_size_max = 0;
  for (auto element : result_storage) {
    if (element > 1) {
      counter[element]++;
    }
    if (element_size_max < element) {
      element_size_max = element;
    }
  }
  printf("scale: %2ld, max: %d ", scale_size, element_size_max);
  for (int i = 2; i < 8; i++) {
    if (counter[i]) {
      printf(" %d: %3d", i, counter[i]);
    }
  }
  puts("");
  result_storage.clear();
  counter.clear();
}

int main(int _argc, char const *_argv[]) {
  assert((length & 1) == 0);
  assert(length > 1024);

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

  // printf("%zu %zu\n", population_vector.size(), length);

  assert(population_vector.size() == length);

  original_vector = population_vector;

  sample_vector = std::vector<unsigned long long>(
      original_vector.begin(), original_vector.begin() + sample_length);
  sample_vector.push_back(min_value);
  sample_vector.push_back(max_value);

  std::sort(sample_vector.begin(), sample_vector.end());

  for (int i = 2; i <= 16; i++) {
    mian(i);
  }
}