Submission #75815673

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define MOD 1000000007
#define INF 987654321
#define PI 3.1415926535

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<int> a(n), b(m);
    vector<int> cnt(1000001, 0);

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }

    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
    }

    bool done = false;

    vector<int> ans;
    for (int i = 0; i < m; i++)
    {
        if (cnt[b[i]] > 0)
        {
            ans.push_back(b[i]);
            cnt[b[i]]--;
        }
        else
        {
            done = true;
            break;
        }
    }

    if (!done)
    {
        vector<int> pi(m, 0);
        int idx = 0;
        for (int i = 1; i < m; i++)
        {
            while (idx > 0 && b[i] != b[idx])
            {
                idx = pi[idx - 1];
            }
            if (b[i] == b[idx])
            {
                pi[i] = ++idx;
            }
        }

        idx = pi[m - 1];
        while (true)
        {
            for (int i = idx; i < m; i++)
            {
                if (cnt[b[i]] > 0)
                {
                    ans.push_back(b[i]);
                    cnt[b[i]]--;
                }
                else
                {
                    done = true;
                    break;
                }
            }
            if (done)
                break;
        }
    }

    for (int i = 0; i <= 1000000; i++)
    {
        while (cnt[i] > 0)
        {
            ans.push_back(i);
            cnt[i]--;
        }
    }

    for (int an : ans)
    {
        cout << an << ' ';
    }
}

Submission Info

Judge Result