Algorithms : add 01-algorithmic_toolbox 03-divide_and_conquer

3 files changed, 28 insertions, 0 deletions

diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
new file mode 100644
index 0000000..efc7a82
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/inversions.cpp
@@ -0,0 +1,25 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+
+long long get_number_of_inversions(vector<int> &a, vector<int> &b, size_t left, size_t right) {
+  long long number_of_inversions = 0;
+  if (right <= left + 1) return number_of_inversions;
+  size_t ave = left + (right - left) / 2;
+  number_of_inversions += get_number_of_inversions(a, b, left, ave);
+  number_of_inversions += get_number_of_inversions(a, b, ave, right);
+  //write your code here
+  return number_of_inversions;
+}
+
+int main() {
+  int n;
+  std::cin >> n;
+  vector<int> a(n);
+  for (size_t i = 0; i < a.size(); i++) {
+    std::cin >> a[i];
+  }
+  vector<int> b(a.size());
+  std::cout << get_number_of_inversions(a, b, 0, a.size()) << '\n';
+}
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01 b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01
new file mode 100644
index 0000000..b8b0218
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01
@@ -0,0 +1,2 @@
+5
+2 3 9 2 9
diff --git a/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01.a b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01.a
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/01-algorithmic_toolbox/03-divide_and_conquer/04-inversions/tests/01.a
@@ -0,0 +1 @@
+2