#include <iostream>
#include <unordered_set>
#include <iterator>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

void coefficient_gen(int res[], int a_m){
  //res[0] = a_m + 1
  //res[1]  = c
  //res[2] = m

  res[0] = a_m + 1;
  if (a_m % 2 == 1){
    res[2] = a_m * a_m;
    res[1] = a_m - 1;
  }
  else if (a_m % 2 == 0 && a_m % 4 == 0){
    res[2] = a_m * a_m;
    res[1] = a_m - 1;
  }
  else{
    res[2] = (a_m * a_m)/2;
    res[1] = a_m - 1;
  }
}


void lcg(vector<int>& r, int seed, int size, int a, int c, int m){

  if (size == 1){
    r.push_back((a*seed+c)%m);
    return;
  }
  for(int i = 0; i < size; ++i){
    r.push_back(0);
  }
  r[0] = seed;
  for(int i = 1; i < size; ++i){
    r[i] = (a*r[i-1]+c)%m;
  }
  r.erase(r.begin());
}



//b = a-1 is sqrt of period or halfed one
//x = |A|+|B|
//y = |A|/|B|
//i2u is intersection volume to union volume


void generate(vector<int>& set1, vector<int>& set2, int seed, int b, double i2u, double y){
  int acm[3];
  coefficient_gen(acm, b);
  int i = int(round(i2u*acm[2]));
  double proportion = (acm[2]*y-i)/(acm[2]-i*y);
  vector<int> uniSet;
  lcg(uniSet, seed, acm[2] + i, acm[0], acm[1], acm[2]);
  vector<int>::iterator setWalker1 = uniSet.begin();
  vector<int>::iterator setWalker2 = uniSet.end();
  while(setWalker1 != uniSet.begin() + i - 1 ){
    set1.push_back(*setWalker1);
    ++setWalker1;
  }
  setWalker2 = setWalker1;

  while(setWalker2 != uniSet.end() - i + 1){
    ++setWalker2;
  }
  //random_shuffle(setWalker1, setWalker2);
  int siA = int((setWalker2-setWalker1)*proportion);

  for(int j = 0; j < siA; ++j){
    set1.push_back(*setWalker1);
    ++setWalker1;
  }
  while(setWalker1 != setWalker2){
    set2.push_back(*setWalker1);
    ++setWalker1;
  }
  while(setWalker1 != uniSet.end()){
    set2.push_back(*setWalker1);
    ++setWalker1;
  }
  //random_shuffle(set1.begin(), set1.end());
  //random_shuffle(set2.begin(), set2.end());


}



vector<int>::iterator binary_search_iterated(vector<int>* arr, vector<int>::iterator low, vector<int>::iterator high, int x){
    if (high >= low){
        vector<int>::iterator mid = low + (high - low)/2;

        if (*mid == x){
            return mid;
        }
        else{
            if (*mid > x){
                return binary_search_iterated(arr, low, mid - 1, x);
            }
            else{
                return binary_search_iterated(arr, mid + 1, high, x);
            }
        }

    }
    else{
        return low;
    }

}



void BaezaYates_step(vector<int>* A, vector<int>* B, vector<int>::iterator A_begin, vector<int>::iterator A_end, vector<int>::iterator B_begin, vector<int>::iterator B_end, unordered_set<int> *C, int i = 0){

    if (A_end - A_begin <= 0 || B_end - B_begin <= 0){
        return;
    }
    vector<int>::iterator midB = B_begin + (B_end - B_begin)/2;
    int midBval = *midB;
    vector<int>::iterator midA = binary_search_iterated(A, A_begin, A_end, midBval);
    vector<int>::iterator a_res,b_res;
    cout <<i<<endl;
    if ((midA-A_begin) > (midB-B_begin)){
        cout << A_end - A_begin << endl << B_end - B_begin;

        cout<<endl;

        BaezaYates_step(A,B,A_begin, midA, B_begin, midB, C, i+1);
    }
    else{
      cout << A_end - A_begin << endl << B_end - B_begin;


        cout<<endl;
        BaezaYates_step(B,A,B_begin, midB, A_begin, midA, C, i+1);
    }
    if (*midA == midBval){
        cout << "Inserted\n\n\n";
        C->insert(midBval);
    }
    if ((A_end - midA) > (B_end - midB)){
      cout << A_end - A_begin << endl << B_end - B_begin;

        cout<<endl;
        BaezaYates_step(A,B,midA+1, A_end, midB+1, B_end, C, i+1);
    }
    else{
      cout << A_end - A_begin << endl << B_end - B_begin;

        cout<<endl;
        BaezaYates_step(B,A,midB+1, B_end, midA+1, A_end, C, i+1);
    }

}

int main(){

  int res[3];
  vector<int> lcg_res;

  coefficient_gen(res, 14);

  cout << res[0] << ' ' << res[1] << ' ' << res[2] << endl;
  vector<int>  s1;
  vector<int>  s2;

  generate(s1, s2, 14,30000,0.8, 1);

  cout << s1.size() << ' ' << s2.size() << endl;

  unordered_set<int> c;

  //BaezaYates_step(s1, s2, s1.begin(), s1.end(), s2.begin(), s2.end(), &c);

  return 0;
}