#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;
}