#include<bits/stdc++.h>
#include <sys/time.h>
using namespace std;
using pi=pair<int,int>;
long long get_rand(long long lim,mt19937_64 &eg){
return (long long)(eg()%lim);
}
long long start_time;
void start_clock(){
struct timeval tv;
gettimeofday(&tv, NULL);
start_time=(tv.tv_sec*1000000+tv.tv_usec);
}
long long current_clock(){
struct timeval tv;
gettimeofday(&tv, NULL);
long long current_time=(tv.tv_sec*1000000+tv.tv_usec);
long long res=current_time-start_time;
// cout << res/1000000 << ".";
// cout << res%1000000 << " sec\n";
return res;
}
int main(){
uint_fast64_t seed=1;
mt19937_64 engine(seed);
for(int i=0;i<100000;i++){engine();}
int kind=500000;
int elem=5000000;
int exe_time=10;
long long tvv_g=0,tvv_w=0;
long long tpv_g=0,tpv_w=0;
for(int exe=0;exe<exe_time;exe++){
vector<int> arr(elem);
for(auto &nx : arr){nx=get_rand(kind,engine);}
vector<int> p(kind);
for(int i=0;i<kind;i++){p[i]=i;}
shuffle(p.begin(),p.end(),engine);
// cout << "vector<vector<int>>:\n";
start_clock();
vector<vector<int>> vv(kind+5);
for(int i=0;i<elem;i++){
vv[arr[i]].emplace_back(i);
}
// cout << "generate: ";
tvv_g+=current_clock();
start_clock();
int hash1=0;
for(int i=0;i<kind;i++){
int chash=0;
for(auto &nx : vv[i]){
chash+=nx;
chash&=32767;
}
hash1^=(chash<<(i&15));
}
// cout << "walkthrough: ";
tvv_w+=current_clock();
// cout << "vector<pair<int,int>>:\n";
start_clock();
int add_point=kind;
vector<pi> pv(kind+elem+5,{-1,-1});
for(int i=0;i<elem;i++){
if(pv[arr[i]].first!=-1){
pv[add_point]=pv[arr[i]];
pv[arr[i]].second=add_point;
add_point++;
}
pv[arr[i]].first=i;
}
// cout << "generate: ";
tpv_g+=current_clock();
start_clock();
int hash2=0;
for(int i=0;i<kind;i++){
int chash=0;
int pos=i;
while(pos!=-1 && pv[pos].first!=-1){
chash+=pv[pos].first;
chash&=32767;
pos=pv[pos].second;
}
hash2^=(chash<<(i&15));
}
// cout << "walkthrough: ";
tpv_w+=current_clock();
assert(hash1==hash2);
}
double output;
cout << "vector<vector<int>>:\n";
output=tvv_g;
output/=1000;output/=exe_time;
cout << "generate: " << output << " ms\n";
output=tvv_w;
output/=1000;output/=exe_time;
cout << "walkthrough: " << output << " ms\n";
cout << "\n";
cout << "vector<pair<int,int>>:\n";
output=tpv_g;
output/=1000;output/=exe_time;
cout << "generate: " << output << " ms\n";
output=tpv_w;
output/=1000;output/=exe_time;
cout << "walkthrough: " << output << " ms\n";
return 0;
}