1

Условие задачи:

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

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

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

#include <bits/stdc++.h>
using namespace std;

bool dp[100001];

int main()
{
    int n, m;
    cin >> n >> m;
    for (size_t i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        dp[x] = true;
    }
    vector<int> ans;
    for (size_t i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        if (dp[x])
            ans.push_back(x);
    }
    sort(ans.begin(), ans.end());
    for (auto& b : ans)
        cout << b << " ";
}

Решил сделать все с помощью запоминания чисел. Однако данное решение засчитывается как неверное. А контр-пример найти мне не удалось. В чем может быть проблема?

И параллельный вопрос: я объявляю массив dp однако он автоматически инициализируется нулями. А почему? По идее не должен же?...

4
  • 3
    Вы объявили массив как глобальную переменную - значит, должен обнуляться.
    – Harry
    2 июл 2020 в 2:53
  • 1
    Контрпример 1 2 \n 1 1 1. Результат должен быть 1 а не 1 1
    – extrn
    2 июл 2020 в 3:00
  • @extrn точно! вы правы, сейчас подправлю свою программу...
    – Learpcs
    2 июл 2020 в 3:01
  • также желательно резервировать память для вектора, чтобы избежать перераспределений памяти и много копирования
    – Ildar
    2 июл 2020 в 7:34

1 ответ 1

1
#include <bits/stdc++.h>
using namespace std;

bool dp[100001];

int main()
{
    int n, m;
    cin >> n >> m;
    for (size_t i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        dp[x] = true;
    }
    vector<int> ans;
    for (size_t i = 0; i < m; i++)
    {
        int x;
        cin >> x;
        if (dp[x])
        {
            ans.push_back(x);
            dp[x] = false; //<--- решение
        }

    }
    sort(ans.begin(), ans.end());
    for (auto& b : ans)
        cout << b << " ";
}

спасибо @extrn

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.