1 files changed, 102 insertions, 0 deletions

diff --git a/expt_0702.cpp b/expt_0702.cpp
new file mode 100644
index 0000000..f7023f7
--- /dev/null
+++ b/expt_0702.cpp
@@ -0,0 +1,102 @@
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <cstdio>
+#include <iostream>
+#include <numeric>
+#include <string>
+#include <vector>
+
+constexpr size_t length = 1048576;
+std::vector<unsigned long long> population_vector, sample_vector,
+    original_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(const long sample_length) {
+  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 = length / (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());
+}
+
+void mian(const long sample_length, const long split_size) {
+  sample_vector = std::vector<unsigned long long>(
+      original_vector.begin(), original_vector.begin() + sample_length);
+  result_storage.resize(sample_length, std::vector<unsigned long long>());
+
+  sample_vector.push_back(population_vector[0]);
+  sample_vector.push_back(*(population_vector.cend() - 1));
+  std::sort(sample_vector.begin(), sample_vector.end());
+  const auto slice_size = 1.0 / (long double)split_size;
+
+  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("\n%Lf\n", calc_stddev(sample_length));
+  result_storage.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;
+       population_vector.push_back(i))
+    ;
+  fclose(file);
+
+  assert(population_vector.size() == length);
+
+  original_vector = population_vector;
+
+  std::sort(population_vector.begin(), population_vector.end());
+  auto sample_length = 0, split_size = 0;
+  while (std::cin >> sample_length >> split_size) {
+    mian(sample_length, split_size);
+  }
+}
\ No newline at end of file