Пересечение множеств

Эта задача сложна своими ограничениями. Самое ресурсоемкое, но простое решение, которое может прийти в голову - это считать данные в массивы, исключить из них повторяющиеся элементы, далее пробегая по одному из них смотреть: есть ли он во втором и если есть, то выводить в выходной файл. Здесь только исключение повторящихся элементов может при неэффективном решении иметь сложность O(n²), что для миллиона элементов может вызвать TLE (Time limit exceeded).

Рассмотрим теперь верное решение этой задачи. Здесь вовсе не нужны два массива, длина которых может быть до миллиона. В силу конечности диапазона возможных значений мы можем описать некоторый массив a[i] для i=0..10⁵, в i-м значении будем хранить 0, если число i не содержится ни в одном из двух наборов чисел. Если число i имеется в первом наборе, то запишем туда 1, а если и в обоих наборах, то запишем туда 2. После чего пробегая по массиву нужно будет вывести все i, у которых a[i]=2. Заполнение массива a[i] происходит следующим образом: сначала все элементы обнуляются, далее при чтении элемента x первого набора можно выполнять присваивание a[x]=1. При просмотре элементов второго набора для каждого элемента y можно a[y]=2 только в том случае, когда a[y]=1.

Приведенный выше алгоритм можно формализовать к следующему виду:

int a[0..105]={0...0};

read(n,m);
for i=1..n{
  read(x);
  a[x]=1;
}
for i=1..m{
  read(y);
  if(a[y]==1) a[y]=2;
}
for i=0..105{
  if(a[i]==2) write(i,' ');
}

[Обсуждение] [Все попытки] [Задача]