#include <iostream>
#include <unordered_set>
#include <set>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <cstring>

using namespace std;

#define MAX_SIZE (100000000)

// iterator to praktycznie wskaźnik; można go przesuwać po elementach przez ++ i --
// "*iterator" to dereferencja "wskaźnika", czyli dostęp do wartośći, na którą pokazuje.
//to samo co pascalowskie "iterator^"

template <class iter>
iter stable_unique_1 ( iter first, iter last )
{
    unordered_set<int> temp; //zbiór użytych, pusty na poczatku
    iter writer(first); //tym będziemy czytac kazdy element
    iter reader(first); // tu bedziemy zapisywac tylko unikalne. poczatkowo oba wskazniki idą razem
    while (reader!= last) { //czy to już koniec
        if (temp.count(*reader)==0){  //element pokazywany przez reader nie istenije w temp
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            temp.insert(*reader); //dodajemy do zbioru już użytych
        }
        reader++;// kroczek
    }
    return writer; // zwracam iterator (wskaźnik) za ostatnim sensownym elementem,
    //nie zmieniam wielkośći tablicy, tym sie zajme poziom wyzej,
    //taka konwencja, patrz idiom remove-erase
}


template <class iter>
iter stable_unique_2 ( iter first, iter last )
{
    set<int> temp; //zbiór użytych
    iter writer(first);
    iter reader(first);
    while (reader!= last) { //czy to już koniec
        if (temp.count(*reader)==0){  //element pokazywany przez reader nie istenije ww temp
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            temp.insert(*reader); //dodajemy do zbioru już użytych
        }
        reader++;// kroczek
    }
    return writer;
}

template <class iter>
iter stable_unique_3 ( iter first, iter last )
{
    iter writer(first);
    iter reader(first);
    while (reader!= last)  //czy to już koniec
    {
        if (count(first, writer, *reader)==0){  //elementu poszukiwany (wskazywany przez reader) nie ma
                                                  //w już przetworzonym zakresie (od [first a przed writer)
                                                //lepiej byłoby użyć funkcji find:
                                                //find(first, writer, *reader)==writer) ale warunek trochę zaciemnia:)
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
        }
        reader++;// kroczek
    }
    return writer;
}

template <class iter>
iter stable_unique_4 ( iter first, iter last )
{
    unordered_set<int> temp(first, last); //zbiór nieużytych
    iter writer(first);
    iter reader(first);
    while (reader!= last) { //czy to już koniec
        if (temp.count(*reader)>0){  //element pokazywany przez reader istenije w temp
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            temp.erase(*reader); //dodajemy do zbioru już użytych
        }
        reader++;// kroczek
    }
    return writer;
}


template <class iter>
iter unstable_unique ( iter first, iter last )
{
    sort(first, last);
    return unique(first, last);
}


template <class iter>
iter stable_unique_5 ( iter first, iter last )
{
    vector <int> sorted(first, last);
    vector <uint8_t> visited(sorted.size(),0);
    sort(sorted.begin(), sorted.end());

    iter writer(first);
    iter reader(first);
    while (reader!= last) { //czy to już koniec
        auto it = lower_bound(sorted.begin(), sorted.end(),*reader);
        if ( visited[ it-sorted.begin() ]==0  ){
            *writer=*reader; // kopiuj unikalny element na pierwsze należne miejsce
            writer++; //przesuń owo miejsce
            visited[ it-sorted.begin() ] = 1;
        }
        reader++;// kroczek
    }
    return writer;

}





class stoper
{
    chrono::time_point<chrono::high_resolution_clock> a,b;
public:
    void start(){a = chrono::high_resolution_clock::now();}
    void stop() {b = chrono::high_resolution_clock::now();}
    double value()
    {
        chrono::duration<double> elapsed_seconds = b-a;
        return elapsed_seconds.count();
    }
};


template <typename F >
void test (F f, string s,int size)
{

    if( size == 100 ) {
        vector<int> tab = {12,457,12,457,1,56,89,12,11,11,55,11,11,1,457};
        tab.erase( f( tab.begin(),tab.end() ), tab.end()  );
        cout<<s<<endl<<"poprawność:"<<endl; ;
        for (auto a:tab)
            cout<<a<<" ";
        cout<<endl;
    }


    {
        vector<int> tab ;

        random_device rd;
        mt19937 gen(rd());

        tab.resize(size);
        generate(tab.begin(), tab.end(), gen);
        stoper st;   st.start();
        tab.erase( f( tab.begin(),tab.end() ), tab.end()  );
        st.stop();
        cout<<size<<" zajelo "<<st.value()<<"s"<<endl;
    }

    if( size == MAX_SIZE ) cout << endl;


}

static unsigned int hash_mm( const int x , const unsigned int s2) {
    const unsigned int xx = (unsigned int)x;
    return ( (xx*67523u + 31237u) ^ (xx*78529u + 96285u) ) % s2;
}

static bool exist_mm( const int x , int u[] , const unsigned int s2 ) {
    unsigned int i = hash_mm( x , s2 );
    while( u[i] != x && u[i] != 0 )
        i = (i+1)%s2;
    if( u[i] == 0 ) {
        u[i] = x;
        return false;
    }
    return true;
}

static int uniq_mm( int t[], const int size ) {
    const unsigned int s2 = (unsigned int)(size/2*5+2);
    int *u = new int[s2];
    memset( u , 0 , s2 * sizeof(int) );
    int size2 = 0;
    bool zero = 0;
    for( int i=0 ; i<size ; i++ ) {
        if( !zero && t[i] == 0 ) {
            t[size2++] = t[i];
            zero = true;
        } else if( ! exist_mm( t[i] , u , s2) ) {
            t[size2++] = t[i];
        }
    }

    delete[] u;
    return size2;
}

//template <class ForwardIterator, class Generator>
//  void generate ( ForwardIterator first, ForwardIterator last, Generator gen ) !!! nie ma referencji na generator? jest referencja na rd w rd???
//{
//  while (first != last) {
//    *first = gen();
//    ++first;
//  }
//}


static void generate( int t[], const int size , mt19937 gen )
{
  for( int i=0 ; i<size ; i++ )
      t[i] = gen();
}

static void test_mm( int size )
{
    if( size == 100 )
    {
        cout<<"samorobka"<<endl<<"poprawność:"<<endl; ;
        int tab[] = {12,457,12,457,1,56,89,12,11,11,55,11,11,1,457};
        int size2 = uniq_mm( tab , sizeof(tab)/sizeof(tab[0]) );

        for (int i=0 ; i<size2 ; i++ )
            cout<<tab[i]<<" ";
        cout<<endl;
    }

    {
        random_device rd;
        mt19937 gen(rd());

        int *tab = new int[size];
        generate( tab , size , gen );
        stoper st;
        st.start();
        uniq_mm( tab , size );
        st.stop();
        cout<<size<<" zajelo "<<st.value()<<"s"<<endl;
        delete[] tab;
    }

    if( size == MAX_SIZE ) cout << endl;
}


int main()
{


    typedef vector<int>::iterator iter;
    for( int s=100 ; s<=MAX_SIZE ; s*=10 )
        test_mm( s );
    for( int s=100 ; s<=MAX_SIZE/10 ; s*=10 )
        test(  stable_unique_1<iter> ,"hashmapa budowana" , s );
    for( int s=100 ; s<=MAX_SIZE/10 ; s*=10 )
        test(  stable_unique_2<iter> , "zbior budowany" , s );
    for( int s=100 ; s<=MAX_SIZE/10 ; s*=10 )
        test(  stable_unique_4<iter> , "hashmapa usuwana " , s );
    for( int s=100 ; s<=MAX_SIZE ; s*=10 )
        test(  unstable_unique<iter> , "sortowanie "  , s);
    for( int s=100 ; s<=MAX_SIZE/10 ; s*=10 )
        test(  stable_unique_5<iter> , "sortowanie stab" , s );
    return 0;
}