#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <chrono>

class muTimer
{
    using Clock = std::chrono::high_resolution_clock;
    bool active = false;
    Clock::duration   duration_;
    Clock::time_point start_ = Clock::now(), stop_ = Clock::now();

    muTimer(const muTimer&)             = delete;
    muTimer& operator=(const muTimer&)  = delete;
public:
    using ns       = std::chrono::nanoseconds;
    using mks      = std::chrono::microseconds;
    using ms       = std::chrono::milliseconds;
    muTimer() { reset(); start(); }
    ~muTimer() = default;
    muTimer& reset()
    {
        duration_ = std::chrono::nanoseconds(0);
        active    = false;
        return *this;
    }
    muTimer& start()
    {
        if (!active)
        {
            start_ = Clock::now();
            active = true;
        }
        return *this;
    }
    muTimer& stop()
    {
        if (active)
        {
            stop_      = Clock::now();
            duration_ += stop_ - start_;
            active     = false;
        }
        return *this;
    }
    template<typename T = mks>
        unsigned long long duration()
    {
        return static_cast<unsigned long long>
            (std::chrono::duration_cast<T>(stop_-start_).count());
    }
};

using namespace std;


int main()
{
    const int N = 1000;
    vector<int> y(N), z(N);
    for(int i = 0; i < N; ++i)
        y[i] = z[i] = rand()%200;

    {
        muTimer mt;
        sort(y.begin(),y.end());
        mt.stop();
        cout << "Sorting  : " << mt.duration<>() << " mks\n";
    }
    {
        muTimer mt;
        auto p = partition(z.begin(),z.end(),[](int x) { return x < 50; });
        p = partition(p,z.end(),[](int x) { return x < 100; });
        p = partition(p,z.end(),[](int x) { return x < 150; });
        mt.stop();
        cout << "Partition: " << mt.duration<>() << " mks\n";
    }

    cout << endl;

    auto p1 = partition_point(y.begin(),y.end(),[](int x) { return x < 50; });
    auto p2 = partition_point(z.begin(),z.end(),[](int x) { return x < 50; });

    cout << p1 - y.begin() << " vs " << p2 - z.begin() << endl;

    p1 = partition_point(y.begin(),y.end(),[](int x) { return x < 100; });
    p2 = partition_point(z.begin(),z.end(),[](int x) { return x < 100; });

    cout << p1 - y.begin() << " vs " << p2 - z.begin() << endl;

    p1 = partition_point(y.begin(),y.end(),[](int x) { return x < 150; });
    p2 = partition_point(z.begin(),z.end(),[](int x) { return x < 150; });

    cout << p1 - y.begin() << " vs " << p2 - z.begin() << endl;

}