#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <chrono>
#include <iterator>
using namespace std;
multiset<int> HW(const multiset<int>& a, const multiset<int>& b)
{
multiset<int> c (a);
c.insert(b.begin(),b.end());
return c;
}
multiset<int> AnT(const multiset<int>& a, const multiset<int>& b)
{
multiset<int> c = a;
auto it_hint = c.begin();
for (const int &src : b)
{
it_hint = c.insert(it_hint, src);
++it_hint;
}
return c;
}
multiset<int> AnTmerge(const multiset<int>& a, const multiset<int>& b)
{
multiset<int> c;
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c, c.end()));
return c;
}
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());
}
};
int main(int argc, const char * argv[])
{
multiset<int> a;
multiset<int> b;
for(int i = 0; i < 1000'000; ++i)
{
a.insert(rand());
b.insert(rand());
}
multiset<int> c, d, e;
{
muTimer mt;
c = HW(a,b);
mt.stop();
cout << mt.duration() << endl;
}
{
muTimer mt;
c = AnT(a,b);
mt.stop();
cout << mt.duration() << endl;
}
{
muTimer mt;
c = AnTmerge(a,b);
mt.stop();
cout << mt.duration() << endl;
}
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGl0ZXJhdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCm11bHRpc2V0PGludD4gSFcoY29uc3QgbXVsdGlzZXQ8aW50PiYgYSwgY29uc3QgbXVsdGlzZXQ8aW50PiYgYikKewogICAgbXVsdGlzZXQ8aW50PiBjIChhKTsKICAgIGMuaW5zZXJ0KGIuYmVnaW4oKSxiLmVuZCgpKTsKICAgIHJldHVybiBjOwp9CgptdWx0aXNldDxpbnQ+IEFuVChjb25zdCBtdWx0aXNldDxpbnQ+JiBhLCBjb25zdCBtdWx0aXNldDxpbnQ+JiBiKQp7CiAgICBtdWx0aXNldDxpbnQ+IGMgPSBhOwoKICAgIGF1dG8gaXRfaGludCA9IGMuYmVnaW4oKTsKICAgIGZvciAoY29uc3QgaW50ICZzcmMgOiBiKQogICAgewogICAgICAgIGl0X2hpbnQgPSBjLmluc2VydChpdF9oaW50LCBzcmMpOwogICAgICAgICsraXRfaGludDsKICAgIH0KICAgIHJldHVybiBjOwp9CgptdWx0aXNldDxpbnQ+IEFuVG1lcmdlKGNvbnN0IG11bHRpc2V0PGludD4mIGEsIGNvbnN0IG11bHRpc2V0PGludD4mIGIpCnsKICAgIG11bHRpc2V0PGludD4gYzsKICAgIHN0ZDo6bWVyZ2UoYS5iZWdpbigpLCBhLmVuZCgpLCBiLmJlZ2luKCksIGIuZW5kKCksIHN0ZDo6aW5zZXJ0ZXIoYywgYy5lbmQoKSkpOwogICAgcmV0dXJuIGM7Cn0KCmNsYXNzIG11VGltZXIKewogICAgdXNpbmcgQ2xvY2sgPSBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrOwogICAgYm9vbCBhY3RpdmUgPSBmYWxzZTsKICAgIENsb2NrOjpkdXJhdGlvbiAgIGR1cmF0aW9uXzsKICAgIENsb2NrOjp0aW1lX3BvaW50IHN0YXJ0XyA9IENsb2NrOjpub3coKSwgc3RvcF8gPSBDbG9jazo6bm93KCk7CgogICAgbXVUaW1lcihjb25zdCBtdVRpbWVyJikgICAgICAgICAgICAgPSBkZWxldGU7CiAgICBtdVRpbWVyJiBvcGVyYXRvcj0oY29uc3QgbXVUaW1lciYpICA9IGRlbGV0ZTsKcHVibGljOgogICAgdXNpbmcgbnMgICAgICAgPSBzdGQ6OmNocm9ubzo6bmFub3NlY29uZHM7CiAgICB1c2luZyBta3MgICAgICA9IHN0ZDo6Y2hyb25vOjptaWNyb3NlY29uZHM7CiAgICB1c2luZyBtcyAgICAgICA9IHN0ZDo6Y2hyb25vOjptaWxsaXNlY29uZHM7CiAgICBtdVRpbWVyKCkgeyByZXNldCgpOyBzdGFydCgpOyB9CiAgICB+bXVUaW1lcigpID0gZGVmYXVsdDsKICAgIG11VGltZXImIHJlc2V0KCkKICAgIHsKICAgICAgICBkdXJhdGlvbl8gPSBzdGQ6OmNocm9ubzo6bmFub3NlY29uZHMoMCk7CiAgICAgICAgYWN0aXZlICAgID0gZmFsc2U7CiAgICAgICAgcmV0dXJuICp0aGlzOwogICAgfQogICAgbXVUaW1lciYgc3RhcnQoKQogICAgewogICAgICAgIGlmICghYWN0aXZlKQogICAgICAgIHsKICAgICAgICAgICAgc3RhcnRfID0gQ2xvY2s6Om5vdygpOwogICAgICAgICAgICBhY3RpdmUgPSB0cnVlOwogICAgICAgIH0KICAgICAgICByZXR1cm4gKnRoaXM7CiAgICB9CiAgICBtdVRpbWVyJiBzdG9wKCkKICAgIHsKICAgICAgICBpZiAoYWN0aXZlKQogICAgICAgIHsKICAgICAgICAgICAgc3RvcF8gICAgICA9IENsb2NrOjpub3coKTsKICAgICAgICAgICAgZHVyYXRpb25fICs9IHN0b3BfIC0gc3RhcnRfOwogICAgICAgICAgICBhY3RpdmUgICAgID0gZmFsc2U7CiAgICAgICAgfQogICAgICAgIHJldHVybiAqdGhpczsKICAgIH0KICAgIHRlbXBsYXRlPHR5cGVuYW1lIFQgPSBta3M+CiAgICAgICAgdW5zaWduZWQgbG9uZyBsb25nIGR1cmF0aW9uKCkKICAgIHsKICAgICAgICByZXR1cm4gc3RhdGljX2Nhc3Q8dW5zaWduZWQgbG9uZyBsb25nPgogICAgICAgICAgICAoc3RkOjpjaHJvbm86OmR1cmF0aW9uX2Nhc3Q8VD4oc3RvcF8tc3RhcnRfKS5jb3VudCgpKTsKICAgIH0KfTsKCmludCBtYWluKGludCBhcmdjLCBjb25zdCBjaGFyICogYXJndltdKQp7CiAgICBtdWx0aXNldDxpbnQ+IGE7CiAgICBtdWx0aXNldDxpbnQ+IGI7CgogICAgZm9yKGludCBpID0gMDsgaSA8IDEwMDAnMDAwOyArK2kpCiAgICB7CiAgICAgICAgYS5pbnNlcnQocmFuZCgpKTsKICAgICAgICBiLmluc2VydChyYW5kKCkpOwogICAgfQoKICAgIG11bHRpc2V0PGludD4gYywgZCwgZTsKCiAgICB7CiAgICAgICAgbXVUaW1lciBtdDsKICAgICAgICBjID0gSFcoYSxiKTsKICAgICAgICBtdC5zdG9wKCk7CiAgICAgICAgY291dCA8PCBtdC5kdXJhdGlvbigpIDw8IGVuZGw7CiAgICB9CgogICAgewogICAgICAgIG11VGltZXIgbXQ7CiAgICAgICAgYyA9IEFuVChhLGIpOwogICAgICAgIG10LnN0b3AoKTsKICAgICAgICBjb3V0IDw8IG10LmR1cmF0aW9uKCkgPDwgZW5kbDsKICAgIH0KCiAgICB7CiAgICAgICAgbXVUaW1lciBtdDsKICAgICAgICBjID0gQW5UbWVyZ2UoYSxiKTsKICAgICAgICBtdC5zdG9wKCk7CiAgICAgICAgY291dCA8PCBtdC5kdXJhdGlvbigpIDw8IGVuZGw7CiAgICB9Cgp9Cg==