关于#Input#的问题，如何解决？

Description

给定两个整数可重复集合，求两个集合的交集。
Input

输入有两组数据，第一组的第一行为一正整数n，一下n个正整数ai（0 < i <= n）。

第二组的第一行为正整数m，以下m个正整数bi（0 < i <= m）。

其中 1 < n, m <= 32767 0 < ai, bi <= 32767
Output

输出一行，k个正整数，为两组数据构成集合{ai}和{bi}的交集。

输出按第二组数据出现的顺序输出，两数之间使用空格间隔，最后一个数无空格，重复数据只输出一次。

若交集为空，只输出一个0
Sample Input
10
1 2 3 4 5 6 7 8 9 10
10
9 10 11 12 13 14 15 16 17 1
Sample Output
9 10 1

时间超限，时间复杂度为o(n),该怎么改呢

#include 
using namespace std;
int main()
{
        int a[32768], b[32768], A[32768]={0}, c,d, e = 0;
    cin >> c;
    for (int i = 0; i < c; i++)
    {
        cin >> a[i];
        A[a[i]] = 1;
    }
    cin >> d;
    for (int i = 0; i < d; i++)
    {
        cin >> b[i];
    }
    for (int i = 0; i < d; i++)
    {
        if (A[b[i]] == 1)
        {
            if (e != 0)
            {
                cout << " ";
            }
            e++;
            cout<< b[i];
        }
    }
    if (e == 0)
    {
        cout << e;
    }
 
    return 0;
}
 

#include <iostream>
using namespace std;
int main()
{
    int a[32768], b[32768], A[32768] = {0}, c, d, e = 0;
    cin >> c;
    for (int i = 0; i < c; i++)
    {
        cin >> a[i];
        A[a[i]] = 1;
    }
    cin >> d;
    for (int i = 0; i < d; i++)
    {
        cin >> b[i];
    }
    for (int i = 0; i < d; i++)
    {
        if (A[b[i]] == 1)
        {
            if (e != 0)
            {
                cout << " ";
            }
            e++;
            cout << b[i];
            A[b[i]] = 0; // 标记该数字已输出
        }
    }
    if (e == 0)
    {
        cout << "0";
    }

    return 0;
}

谁让我正确，我给谁采纳

参考GPT和自己的思路：你的代码时间复杂度为 $O(n)$，其中 $n$ 为输入数据量，但是题目中给出的数据量最大为 $32767$，这是无法通过本题的。所以需要优化算法，将时间复杂度降为 $O(n\log n)$ 或更低。

可以使用集合（set）数据结构，将两个集合分别存储到两个 set 中，然后对其中一个 set 进行遍历，对于每个元素，判断它是否在另一个 set 中出现，如果出现则输出。这样可以将时间复杂度降为 $O(n\log n)$，可以通过本题。

代码示例：

#include <iostream>
#include <set>
using namespace std;
int main()
{
int n, m, x;
set<int> s1, s2, ans;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
s1.insert(x);
}
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> x;
s2.insert(x);
}
for (auto it = s2.begin(); it != s2.end(); it++)
{
if (s1.count(*it) > 0)
{
ans.insert(*it);
}
}
if (ans.empty())
{
cout << 0 << endl;
}
else
{
for (auto it = ans.begin(); it != ans.end(); it++)
{
cout << *it << " ";
}
}
return 0;
}