void lcg(vector<unsigned int>& r, int seed, int size, unsigned long a, unsigned long c, unsigned long 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] = uint32_t((a*r[i-1]+c)%m);
  }
  r.erase(r.begin());
}



void generate(int seed, long size, double a2b, double i2u, vector<unsigned int> & a, vector<unsigned int>& b){
//hardcoded consts for lcg generator
//a = 50001
//c = 49999
//m = 2500000000
int inter = int(size*i2u);
int a_size = int(a2b*size*(1-i2u)/(a2b+1))+inter;
int b_size = int(size*(1-i2u)/(a2b+1))+inter;
lcg(a, seed, a_size, 50001, 49999, 2500000000);
lcg(b, a[a_size - inter],b_size, 50001, 49999, 2500000000);
}

void generate_v3_0(int seed, long sizeA, long sizeB, long sizeInter, vector<unsigned int> & a, vector<unsigned int>& b) {
//hardcoded consts for lcg generator
//a = 50001
//c = 49999
//m = 2500000000


lcg(a, seed, sizeA+1, 50001, 49999, 2500000000);
(sizeA!=sizeInter)?lcg(b, a[sizeA-sizeInter-1], sizeB+1, 50001, 49999, 2500000000):lcg(b, seed, sizeB+1, 50001, 49999, 2500000000);

std::shuffle(a.begin(), a.end(), std::default_random_engine(seed+1));
std::shuffle(b.begin(), b.end(), std::default_random_engine(seed+2));
}









//тестер

int main(int argc, char* argv[]) {
  std::ofstream out;
  vector<unsigned int> a;
  vector<unsigned int> b;


  /*
  1000
  2000
  5000
  10000
  20000
  50000
  100000
  200000
  500000
  1000000
  2000000
  5000000
  10000000

  */
  int A = 100000;
  int B = 100000;
  int inter = 10000;
  if (argc>1){
    A = stoi(argv[1]);
    B = stoi(argv[2]);
    inter = stoi(argv[3]);

  }

  generate_v3_0(14, A, B, inter, a, b);




  //unordered_set<unsigned int> v_intersection;
  /*
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

   BaezaYates_step(&a, &b, a.begin(), a.end(), b.begin(), b.end(), &v_intersection);
  */

  vector<unsigned int> res;






  double start_time = getCPUTime();
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());


  double preprocess_time = getCPUTime();


  GallopingIntersection(a, b, res);


  double end_time = getCPUTime();

  cout << "Intersection size: " << res.size() << endl; // ' ' << v_intersection.size() << endl;
  cout << "Union size: " << A + B - inter << endl;
  cout << "A: " << a.size() << " B: " << b.size();
  cout << "\nCPU time: " << end_time - start_time;
  cout << "\nCPU preprocess time: " << preprocess_time - start_time << endl;



}