#include <stdio.h>
#include <vector>
#include <set>
#include <random>
#include <bitset>
#include <unordered_set>
#include <x86intrin.h>
#include <algorithm>


std::vector<int> arr;

//Задать возможно одинаковые
void reset(int n,int a,int b){
    arr.resize(n);
    std::default_random_engine gen(_rdtsc());
    std::uniform_int_distribution<int> ds(a,b);
    for (int i=0;i<n;i++)
        arr[i]=ds(gen);
}

//Задать точно случайные
void reset_sl(int n,int a,int b){
    std::default_random_engine gen(_rdtsc());
    std::uniform_int_distribution<int> ds(a,b);
    std::unordered_set<int> brr(n);
    while (brr.size()<n)
        brr.insert(ds(gen));
    arr.clear();
    arr.insert(arr.begin(),brr.cbegin(),brr.cend());
}

//Через размер set
bool test_1(){
    std::set brr(arr.begin(),arr.end());
    return arr.size()==brr.size();
}

//Через миллиард элементов
bool test_2(){
    std::vector<char> brr(1000000000,0);
    for (int i=0;i<arr.size();i++)
        if (brr[arr[i]])
            return false;
        else
            brr[arr[i]]=1;
    return true;
}

//Через миллиард bool
bool test_3(){
    std::vector<bool> brr(1000000000,false);
    for (int i=0;i<arr.size();i++)
        if (brr[arr[i]])
            return false;
        else
            brr[arr[i]]=true;
    return true;
}

//Через сортировку без дополнительной памяти
bool test_4(){
    sort(arr.begin(),arr.end());
    for (int i=0;i<arr.size()-1;i++)
        if (arr[i]==arr[i+1])
            return false;
    return true;
}

void timeit(int n,int a,int b,bool(*te)(void),const char* name){
    size_t t1,t2;
    constexpr int N=5;
    constexpr double mod=1.0/(N-1);
    double t;

    printf("%s[%d]={'n':[],'s':[]}\n",name,n);

    t=0;
    for (int i=0;i<N;i++){
        reset(n,a,b);
        t1=_rdtsc();
        te();
        t2=_rdtsc();
        if (i) //Первый замер скипаю, пока там память разогревается
            t+=(t2-t1)*1e-6;
    }
    printf("%s[%d]['n'].append(%.10f)\n",name,n,t*mod);

    t=0;
    for (int i=0;i<N;i++){
        reset_sl(n,a,b);
        t1=_rdtsc();
        te();
        t2=_rdtsc();
        if (i)
            t+=(t2-t1)*1e-6;
    }
    printf("%s[%d]['s'].append(%.10f)\n",name,n,t*mod);

}


int main()
{
    printf("set_i={}\n");
    printf("vector_i={}\n");
    printf("vector_b={}\n");
    for (int i:{10,     30,     90,    271,    815,   2451,   7368,  22143,
          66548, 200000}){
        timeit(i,1,1000000000,test_1,"set_i");
        timeit(i,1,1000000000,test_2,"vector_i");
        timeit(i,1,1000000000,test_3,"vector_b");
        timeit(i,1,1000000000,test_4,"sort");
    }

}