#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <type_traits>
#include <iostream>
#include <mutex>
#include <thread>

template<typename T>
struct AccessCheckVector : public std::vector<T>
{
    const T & operator[](size_t idx) const noexcept
    {
        std::lock_guard lock(mutex);

        for (size_t i = access_marks.size(); i <= idx; i++) {
            access_marks.push_back(false);
        }
        access_marks[idx] = true;

        return this->data()[idx];
    }

    mutable std::vector<bool> access_marks{};
    mutable std::mutex mutex{};
};

uint64_t stable_rand()
{
    static uint64_t state = 42;
    state = state * 6364136223846793005 + 1442695040888963407;
    return state;
}

template<typename T>
T find_max(const std::vector<T> & arr)
{
    T max = 0;
    for (size_t i = 0; i < arr.size(); i++) {
        max = std::max(arr[i], max);
    }
    return max;
}

template<typename T>
T find_max_ass_parallel(const std::vector<T> & arr, size_t threads_num)
{
    std::vector<T> results(threads_num, 0);
    std::vector<std::thread> threads;

    auto worker = [&arr, &results, &threads_num](size_t thread_num) {
        T max = 0;
        for (size_t i = thread_num; i < arr.size(); i += threads_num) {
            max = std::max(arr[i], max);
        }
        results[thread_num] = max;
    };

    for (size_t i = 0; i < threads_num; i++) {
        threads.push_back(std::thread(worker, i));
    }

    for (auto & thread : threads) {
        thread.join();
    }

    /*for (size_t i = 0; i < arr.size(); i++) {
        if (!arr.access_marks[i]) {
            std::cout << "NO ACCESS: " << i << std::endl;
        }
    }*/

    return find_max(results);
}

template<typename T>
float time_delta_ms(T a, T b)
{
    return std::chrono::duration_cast<std::chrono::microseconds>(a - b).count() / 1000.0f;
}

int main()
{
    using Clock = std::chrono::high_resolution_clock;
    using T = uint64_t;

    constexpr size_t N = 1'000'000'000;
    constexpr size_t THREADS_NUM = 4;
    constexpr size_t TESTS_NUM = 4;

    std::vector<uint8_t> arr;
    arr.reserve(N);

    for (size_t i = 0; i < N; i++) {
        arr.push_back(stable_rand() & std::numeric_limits<T>::max());
    }

    for (size_t i = 0; i < TESTS_NUM; i++) {
        auto start = Clock::now();
        auto x = find_max(arr);
        auto end = Clock::now();
        std::cout << "[" << i << "] Serial max = " << static_cast<uint64_t>(x) << "; time = " << time_delta_ms(end, start) << std::endl;

        start = Clock::now();
        x = find_max_ass_parallel(arr, THREADS_NUM);
        end = Clock::now();
        std::cout << "[" << i << "] Ass parallel max = " << static_cast<uint64_t>(x) << "; time = " << time_delta_ms(end, start) << std::endl;
    }

    return EXIT_SUCCESS;
}