#include <cassert>

#include "lib/exec.h"

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

template<typename T>
int partition(vector<T>& v, int left, int right) {
    int mid = (left+right)/2;
    T piv = v[mid];
    while (left <= right) {
        while (v[left] < piv)
            left++;
        while (v[right] > piv)
            right--;
        if (left < right) {
            T b = v[left];
            v[left] = v[right];
            v[right] = b;
            left++;
            right--;
        } else if (left == right) {
            break;
        }
    }
    return left;
}

template<typename T>
void quicksort(vector<T>& v, int start=0, int end=-1) {
    if (end < 0)
        end = v.size()-1;
    if (end-start < 2)
        return;

    int mid = partition(v, start, end);
    quicksort(v, start, mid);
    quicksort(v, mid, end);
}

template<typename T>
void quicksort2(vector<T>& v, int start=0, int end=-1) {
    if (end < 0)
        end = v.size()-1;

    int mid = partition(v, start, end);
    if (mid-1 > start)
        quicksort(v, start, mid);
    if (end > mid)
        quicksort(v, mid, end);
}

template<typename T>
void merge(vector<T>& v, int vlen, vector<T>& w) {
    // v must have space for w.
    assert(v.size()-vlen >= w.size());

    // Pointers to individual arrays.
    int a = vlen-1, b = w.size()-1;
    int i = v.size()-1;

    while (i >= 0) {
        if (v[a] >= w[b]) {
            v[i] = v[a];
            a--;
        } else {
            v[i] = w[b];
            b--;
        }
        i--;
    }

}

void sort_anagram(vector<string>& in) {
    std::sort(in.begin(), in.end(), [](string a, string b) {
            std::sort(a.begin(), a.end());
            std::sort(b.begin(), b.end());
            return a < b;
            });
}

template<typename T>
int shifted_binary_search(const vector<T>& v, const T& elem, int start=0, int end=-1, int off=-1) {
    if (end < 0)
        end = v.size()-1;
    // end is past-the-last element.
    
    if (off < 0) {
        // First find offset.
        int lo = start, mid = (start+end)/2, hi = end;

        while (lo < mid) {
            if (v[mid] > v[hi]) {
                lo = mid;
                mid = (lo+hi)/2;
                continue;
            } else if (v[lo] > v[mid]) {
                hi = mid;
                mid = (lo+hi)/2;
                continue;
            } else {
                break;
            }
        }
        return hi;
    }
    return end;
}

pair<size_t, size_t> heap_children(size_t i) {
    return make_pair(2*i+1, 2*i+2);
}

template<typename T> void heap_sift_down(vector<T>& v, size_t i) {
    if (i >= v.size())
        return;

    pair<size_t, size_t> children = heap_children(i);

    // Special check if we are down in the tree.
    if (get<0>(children) >= v.size())
        return;
    else if (get<1>(children) >= v.size()) {
        size_t left = get<0>(children);
        T& target = v.at(i) > v.at(left) ? v.at(i) : v.at(left);
        swap(target, v.at(i));
        return;
    }

    T& left = v.at(get<0>(children)), &right = v.at(get<1>(children));
    // Order already correct.
    if (max(left, right) < v.at(i))
        return;

    // Recur:
    if (left > right) {
        swap(v.at(i), left);
        heap_sift_down(v, get<0>(children));
    } else {
        swap(v.at(i), right);
        heap_sift_down(v, get<1>(children));
    }
}

template<typename T> void heap_sift_up(vector<T>& v, size_t i) {
    if (i == 0 || i >= v.size())
        return;

    size_t parent_ix = (i-1)/2;
    T& parent = v.at(parent_ix);
    T& current = v.at(i);

    if (parent < current) {
        swap(parent, current);
        heap_sift_up(v, parent_ix);
    }
}

enum class SiftDirection { Up, Down };

template<typename T>
void make_into_heap(vector<T>& v, SiftDirection direction = SiftDirection::Down) {
    if (direction == SiftDirection::Down)
        for (ssize_t i = v.size()-1; i >= 0; i--) {
                heap_sift_down(v, i);
        }
    else
        for (size_t i = 0; i < v.size(); i++) {
                heap_sift_up(v, i);
        }
}


int main(void) {
    vector<string> v{"hello", "olleh", "abc", "bca", "world", "wrlod"};
    vector<int> vi{5,5,6,1,3,2,5,8,9};

    timeit_f([&vi]() -> void { quicksort(vi); }, "quicksort");
    fmt::print("{}\n", vi);
    return 0;
}