feat: Implement expt_0802

Signed-off-by: KunoiSayami <[email protected]>

2 files changed, 64 insertions, 0 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 3bd9244..62d52de 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -93,3 +93,8 @@ set_target_properties(expt_0729 PROPERTIES
 set_target_properties(expt_0729 PROPERTIES CUDA_ARCHITECTURES "75")
 set_target_properties(expt_0726 PROPERTIES LINKER_LANGUAGE CUDA)
 
+
+add_executable(expt_0802 expt_0802.cpp)
+#set_target_properties(expt_0729 PROPERTIES LINKER_LANGUAGE CXX)
+target_link_libraries(expt_0802 m stdc++)
+
diff --git a/expt_0802.cpp b/expt_0802.cpp
new file mode 100644
index 0000000..32727fb
--- /dev/null
+++ b/expt_0802.cpp
@@ -0,0 +1,59 @@
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+vector<vector<int>> a;
+vector<int> result;
+constexpr size_t LENGTH = 2048;
+
+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) {
+  // auto value = result[index + 1];
+  auto real_index = ++index;
+  int step = 0;
+  while (index > 0) {
+    index /= 2;
+    step++;
+  }
+  auto end = (int)std::pow(2, step - 1);
+  auto location = LENGTH / end / 2 * (real_index % end * 2 + 1);
+  if (location == 0) {
+    location = LENGTH;
+  }
+  // printf("%d %d %d %lu %lu\n", step, end, value, real_index % end, location);
+  return location;
+}
+
+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);
+    }
+  }
+  cout << endl;
+
+  for (int i = 0; i < LENGTH; i++) {
+    assert(calculate_location(i) == result[i]);
+  }
+  return 0;
+}