#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <numeric>
#include <vector>

constexpr size_t length = 1048576;
constexpr size_t sample_length = 1024;
constexpr long double slice_size = 1.0 / sample_length;
std::vector<unsigned long long> population_vector, sample_vector;
std::vector<std::vector<unsigned long long>> result_storage;

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

long double calc_stddev() {
  std::vector<size_t> elements;
  std::vector<long double> tmp_vector;
  for (auto &element : result_storage) {
    elements.push_back(element.size());
  }
  tmp_vector.resize(elements.size());
  // auto sum = std::accumulate(elements.begin(),
  // elements.end(),decltype(elements)::value_type(0)); size_t sum = length;
  // printf("\nsum: %ld\n", sum);
  // auto mu = sum / (long double)elements.size();
  long double mu = sample_length;
  // printf("mu: %Lf\n", mu);

  std::transform(elements.begin(), elements.end(), tmp_vector.begin(),
                 [&mu](size_t element) { return std::pow(element - mu, 2); });

  return std::sqrt(std::accumulate(tmp_vector.begin(), tmp_vector.end(),
                                   decltype(tmp_vector)::value_type(0)) /
                   elements.size());
}

int main() {
  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;
       population_vector.push_back(i))
    ;
  fclose(file);

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

  std::vector<unsigned long long> original_vector(population_vector);

  sample_vector = std::vector<unsigned long long>(
      population_vector.begin(), population_vector.begin() + sample_length);

  result_storage.resize(sample_length, std::vector<unsigned long long>());

  std::sort(population_vector.begin(), population_vector.end());
  sample_vector.push_back(population_vector[0]);
  sample_vector.push_back(*(population_vector.cend() - 1));
  std::sort(sample_vector.begin(), sample_vector.end());

  for (auto &element : original_vector) {
    result_storage[(int)safe_ceil(sample_cdf(element) / slice_size) - 1]
        .push_back(element);
    /*auto tmp = sample_cdf(element) / slice_size;
    if (tmp < 1) {
      printf("%lld %Lf ", element, tmp);
    }*/
  }
  for (const auto &element : result_storage) {
    printf("%ld ", element.size());
  }
  printf("%Lf\n", calc_stddev());
}