#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <list>
#include <chrono>
#include <algorithm>
using namespace std;
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());
}
};
list<int> L;
vector<int> V;
int main(int argc, const char * argv[])
{
for(int i = 0; i < 1000000; ++i)
{
int r = rand();
V.push_back(r);
L.push_back(r);
}
L.sort();
sort(V.begin(),V.end());
{
muTimer mu;
long long int sum = 0;
for(int i: V) sum += i;
mu.stop();
cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
}
{
muTimer mu;
long long int sum = 0;
for(int i: L) sum += i;
mu.stop();
cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
}
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxjaHJvbm8+CiNpbmNsdWRlIDxhbGdvcml0aG0+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgbXVUaW1lcgp7CiAgICB1c2luZyBDbG9jayA9IHN0ZDo6Y2hyb25vOjpoaWdoX3Jlc29sdXRpb25fY2xvY2s7CiAgICBib29sIGFjdGl2ZSA9IGZhbHNlOwogICAgQ2xvY2s6OmR1cmF0aW9uICAgZHVyYXRpb25fOwogICAgQ2xvY2s6OnRpbWVfcG9pbnQgc3RhcnRfID0gQ2xvY2s6Om5vdygpLCBzdG9wXyA9IENsb2NrOjpub3coKTsKCiAgICBtdVRpbWVyKGNvbnN0IG11VGltZXImKSAgICAgICAgICAgICA9IGRlbGV0ZTsKICAgIG11VGltZXImIG9wZXJhdG9yPShjb25zdCBtdVRpbWVyJikgID0gZGVsZXRlOwpwdWJsaWM6CiAgICB1c2luZyBucyAgICAgICA9IHN0ZDo6Y2hyb25vOjpuYW5vc2Vjb25kczsKICAgIHVzaW5nIG1rcyAgICAgID0gc3RkOjpjaHJvbm86Om1pY3Jvc2Vjb25kczsKICAgIHVzaW5nIG1zICAgICAgID0gc3RkOjpjaHJvbm86Om1pbGxpc2Vjb25kczsKICAgIG11VGltZXIoKSB7IHJlc2V0KCk7IHN0YXJ0KCk7IH0KICAgIH5tdVRpbWVyKCkgPSBkZWZhdWx0OwogICAgbXVUaW1lciYgcmVzZXQoKQogICAgewogICAgICAgIGR1cmF0aW9uXyA9IHN0ZDo6Y2hyb25vOjpuYW5vc2Vjb25kcygwKTsKICAgICAgICBhY3RpdmUgICAgPSBmYWxzZTsKICAgICAgICByZXR1cm4gKnRoaXM7CiAgICB9CiAgICBtdVRpbWVyJiBzdGFydCgpCiAgICB7CiAgICAgICAgaWYgKCFhY3RpdmUpCiAgICAgICAgewogICAgICAgICAgICBzdGFydF8gPSBDbG9jazo6bm93KCk7CiAgICAgICAgICAgIGFjdGl2ZSA9IHRydWU7CiAgICAgICAgfQogICAgICAgIHJldHVybiAqdGhpczsKICAgIH0KICAgIG11VGltZXImIHN0b3AoKQogICAgewogICAgICAgIGlmIChhY3RpdmUpCiAgICAgICAgewogICAgICAgICAgICBzdG9wXyAgICAgID0gQ2xvY2s6Om5vdygpOwogICAgICAgICAgICBkdXJhdGlvbl8gKz0gc3RvcF8gLSBzdGFydF87CiAgICAgICAgICAgIGFjdGl2ZSAgICAgPSBmYWxzZTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuICp0aGlzOwogICAgfQogICAgdGVtcGxhdGU8dHlwZW5hbWUgVCA9IG1rcz4KICAgICAgICB1bnNpZ25lZCBsb25nIGxvbmcgZHVyYXRpb24oKQogICAgewogICAgICAgIHJldHVybiBzdGF0aWNfY2FzdDx1bnNpZ25lZCBsb25nIGxvbmc+CiAgICAgICAgICAgIChzdGQ6OmNocm9ubzo6ZHVyYXRpb25fY2FzdDxUPihzdG9wXy1zdGFydF8pLmNvdW50KCkpOwogICAgfQp9OwoKCmxpc3Q8aW50PiBMOwp2ZWN0b3I8aW50PiBWOwoKaW50IG1haW4oaW50IGFyZ2MsIGNvbnN0IGNoYXIgKiBhcmd2W10pCnsKICAgIGZvcihpbnQgaSA9IDA7IGkgPCAxMDAwMDAwOyArK2kpCiAgICB7CiAgICAgICAgaW50IHIgPSByYW5kKCk7CiAgICAgICAgVi5wdXNoX2JhY2socik7CiAgICAgICAgTC5wdXNoX2JhY2socik7CiAgICB9CiAgICBMLnNvcnQoKTsKICAgIHNvcnQoVi5iZWdpbigpLFYuZW5kKCkpOwoKICAgIHsKICAgICAgICBtdVRpbWVyIG11OwogICAgICAgIGxvbmcgbG9uZyBpbnQgc3VtID0gMDsKICAgICAgICBmb3IoaW50IGk6IFYpIHN1bSArPSBpOwogICAgICAgIG11LnN0b3AoKTsKICAgICAgICBjb3V0IDw8ICJTdW0gIiA8PCBzdW0gPDwgIiBmb3IgIiA8PCBtdS5kdXJhdGlvbigpIDw8ICIgbWtzXG4iOwogICAgfQogICAgewogICAgICAgIG11VGltZXIgbXU7CiAgICAgICAgbG9uZyBsb25nIGludCBzdW0gPSAwOwogICAgICAgIGZvcihpbnQgaTogTCkgc3VtICs9IGk7CiAgICAgICAgbXUuc3RvcCgpOwogICAgICAgIGNvdXQgPDwgIlN1bSAiIDw8IHN1bSA8PCAiIGZvciAiIDw8IG11LmR1cmF0aW9uKCkgPDwgIiBta3NcbiI7CiAgICB9Cgp9Cg==