Submission #75816124

---

Source Code Expand

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

// https://github.com/skrewbar/cp-templates

#define all(v) (v).begin(), (v).end()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), (v).end())
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
#define by_desc(x) [](const auto& a, const auto& b) { return a.x > b.x; }

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
bool minimize(T& target, T candidate) {
    return target > candidate ? (target = candidate, true) : false;
}
template <typename T>
bool maximize(T& target, T candidate) {
    return target < candidate ? (target = candidate, true) : false;
}

int A[1010101], B[1010101];
int fail[1010101];
int cnt[1010101];

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

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[A[i]]++;
    }
    for (int i = 0; i < M; i++)
        cin >> B[i];

    for (int i = 1, j = 0; i < M; i++) {
        while (j > 0 and B[i] != B[j])
            j = fail[j - 1];
        if (B[i] == B[j])
            fail[i] = ++j;
    }

    int patternLen = M - fail[M - 1];
    for (int i = 0, j = 0; i < N; i++) {
        if (cnt[B[j]]) {
            cout << B[j] << ' ';
            cnt[B[j]]--;
            if (++j >= patternLen)
                j = 0;
        } else
            break;
    }
    for (int v = 0; v <= 1'000'000; v++) {
        for (int c = 0; c < cnt[v]; c++)
            cout << v << ' ';
    }

    return 0;
}

Submission Info

Judge Result