Как решить задачу 82, acmp.ru

Question

Вот условие задачи:

(Время: 1 сек. Память: 64 Мб)

Даны два неупорядоченных набора целых чисел (может быть, с повторениями). Выдать без повторений в порядке возрастания все те числа, которые встречаются в обоих наборах. Входные данные

В первой строке входного файла INPUT.TXT записано через пробел два целых числа N и М (1 ≤ N, М ≤ 300 000) — количество элементов первого и второго наборов, соответственно. Во второй строке записано N чисел первого набора через пробел. В третьей строке записано M чисел второго набора через пробел. Каждое из этих чисел попадает в промежуток от 0 до 105. Выходные данные

В выходной файл OUTPUT.TXT нужно записать в возрастающем порядке без повторений все числа, которые входят как в первый, так и во второй набор. Числа разделять одним пробелом. Если таких чисел нет, то выходной файл должен оставаться пустым.

Можно использовать потоки cin и cout

Уже попробовал несколько решений, такие как: Типо "сортировка подсчётом"

Дальше с помощью set

И с помощью unordered_set

И наконец, с помощью сортировки

Все решения проваливаются или на десятом тесте, или на одинадцатом, с вердиктом: Time limit exceeded Соостветственно не хватает времени, может кто нибудь подскажет более скоростной способ? Использую компилятор: MINGW GNU C++ 14.2.0

Самый быстрый код оказался:

#include <iostream>
#include <vector>
  
using namespace std;
  
int main()
{
    int n,m, t;
    scanf("%i",&n);
    scanf("%i",&m);
    vector<int> a;
    vector<int> b;
    vector<int> c(1000000);
    for(int i = 0; i < n; ++i){
        scanf("%i",&t);
        a.push_back(t);
    }
    for(int i = 0; i < m; ++i){
        scanf("%i",&t);
        b.push_back(t);
    }
    for(int i = 0; i < a.size(); ++i)
        c[a[i]] = 1;
    for(int i = 0; i < b.size(); ++i)
        if(c[b[i]] == 1)
            c[b[i]] = 2;
    for(int i = 0; i < c.size(); ++i){
        if(c[i] == 2)
            printf("%i", i);
        printf(" ");
    }
    return 0;
}

1.25 секунд на 11 тесте

Answer 1

Так намек понятен?

#include <iostream>
#include <fstream>

using namespace std;

unsigned char a[100001], b[100001];

int main(int argc, char * argv[])
{
    ifstream in("input.txt");
    int N, M;
    in >> N >> M;
    for(int d, i = 0; i < N; ++i) { in >> d; a[d] = 1; }
    for(int d, i = 0; i < M; ++i) { in >> d; b[d] = 1; }
    ofstream out("output.txt");
    for(int i = 0; i < 100001; ++i)
    {
        if (a[i] & b[i]) out << i << " ";
    }
}

БЛОГ НА HUSL

Как решить задачу 82, acmp.ru

Ответы (1 шт):