// Даны два массива по n чисел.
// Вывести их a) пересечение
//                   b) объединение
//
//А вот сама программа

#include <stdio.h>
#include <conio.h>

#define N 100

int remove_duplicates(int* mas,int length,int* result);
void show_massive(int* mas,int length);
void sort(int* mas,int length);
int get_intersection(int* mas1,int length1,int* mas2,int length2,int* intersection);
int concat_massives(int* mas1,int length1,int* mas2,int length2,int* association);
void input_massive(const char* massive_name,int* mas,int length);
int input_size();

int main()
{
int a[N];                       // Pervonachal'nye massivy
int b[N];

int proc_a[N];                  // Obrabotannye massivy
int proc_b[N];

int intersect_massive[N];       // Massiv peresechenij
int result_massive[2*N];        // Massiv ob'edinenij

  int n = 0;    //ishodnyj razmer massivov
  int n1 = 0,n2 = 0;    //konechnye razmery massivov a i b
  int OK;

   do
   {
      clrscr();
      puts("Input size");
      fflush(stdin);
      OK=scanf("%d",&n);
   }
   while (!OK);

   input_massive("first",a,n);
   input_massive("second",b,n);

   clrscr();
   puts("Started massive A:");
   show_massive(a,n);
   puts("\nStarted massive B:");
   show_massive(b,n);

   sort(a,n);
   sort(b,n);
   n1 = remove_duplicates(a,n,proc_a);
   n2 = remove_duplicates(b,n,proc_b);

   int intersection_cnt = get_intersection(proc_a,n1,proc_b,n2,intersect_massive);
   puts("\n\nIntersection");
   show_massive(intersect_massive,intersection_cnt);

   int result_cnt = concat_massives(proc_a,n1,proc_b,n2,result_massive);

   sort(result_massive,result_cnt);
   result_cnt = remove_duplicates(result_massive,result_cnt,proc_a);
   puts("\nAssociation:");
   show_massive(proc_a,result_cnt);
   printf("\n");
   fflush(stdin);
   getch();
   return 0;
}

//Udalenie dublikatov
int remove_duplicates(int* mas,int length,int* result)
{
   int j = 0;
   if(!length)
   {
      return 0;
   }
   result[0] = mas[0];
   for (int i = 1;i<length;i++)
   {
      if(result[j] != mas[i])
      {
result[++j] = mas[i];
      }
   }
   return j+1;
}

//Vivod massiva
void show_massive(int * mas,int length)
{
   for (int i = 0;i < length;i++)
   {
      printf("%d ",mas[i]);
   }
}

//Sortirovka
void sort(int *mas,int length)
{
  for(int i = 0; i < length - 1;i++)
   {
      int temp = 0;
      for(int j = i + 1; j < length;j++)
      {
if (mas[i] > mas[j])
{
    temp = mas[i];
    mas[i] = mas[j];
    mas[j] = temp;
}
      }
   }
}

//Peresechenie massivov. (Dvoichnyj poisk)
int get_intersection(int *mas1,int length1,int * mas2,int length2,int *intersection)
{
   int median = 0;
   int intersection_cnt = 0;
   for (int i = 0;i < length1;i++)
   {
      int left_bound = 0;
      int right_bound= length2 - 1;
      do
      {
median = (left_bound + right_bound) / 2;
if (mas1[i] < mas2[median])
{
   right_bound = median - 1;
}
else if (mas1[i] > mas2[median])
{
  left_bound = median + 1;
}
else
{
    intersection[intersection_cnt++] = mas2[median];
    break;
}
      }
      while (left_bound <= right_bound);
   }
   return intersection_cnt;
}

//Soedinenie massivov
int concat_massives(int* mas1, int length1, int* mas2, int length2,int* result_massive)

{
   int i=0;
   for (;i<length1;i++)
   {
      result_massive[i]=mas1[i];
   }
   for (i=0;i<length2;i++)
   {
      result_massive[i+length1]=mas2[i];
   }
   return length1+length2;
}

//Vvod massiva
void input_massive(const char * massive_name,int* mas,int length)
{
   int i;
   int OK;
   for (i=0;i<length;i++)
   {
      printf("%s[%d]",massive_name,i);
      fflush(stdin);
      OK=scanf("%d",mas + i);
      if (!OK) i--;
   }
   mas[length]=0;
}