Submission #75816777

---

Source Code Expand

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
int main() {
    fastio; int N, M; cin >> N >> M;
    vector<int> A(N), B(M), pi(M);
    for (auto &i : A) cin >> i;
    for (auto &i : B) cin >> i;
    for (int i = 1, j = 0; i < M; i++) {
        while (j > 0 && B[i] != B[j]) j = pi[j-1];
        if (B[i] == B[j]) pi[i] = ++j;
    }
    int t = pi[M-1];
    vector<int> v(1e6+1);
    for (auto i : A) v[i]++;
    int m = 1e9;
    map<int,int> mb;
    for (int i = 0; i < M; i++) mb[B[i]]++;
    for (int i = 0; i < M; i++) {
        m = min(m, v[B[i]] / mb[B[i]]);
    }
    vector<int> ans;
    if (m >= 1) {
        for (int i = 0; i < M; i++) {
            v[B[i]]--;
            ans.push_back(B[i]);
        }
    }
    m = 1e9;
    mb.clear();
    for (int i = t; i < M; i++) mb[B[i]]++;
    for (int i = t; i < M; i++) {
        m = min(m, v[B[i]] / mb[B[i]]);
    }
    for (int i = 0; i < m; i++) {
        for (int j = t; j < M; j++) {
            v[B[j]]--;
            ans.push_back(B[j]);
        }
    }
    for (int i = 0; i <= 1e6; i++) {
        if (v[i]) {
            for (int j = 0; j < v[i]; j++) ans.push_back(i);
        }
    }
    for (auto i : ans) cout << i << " ";
    return 0;
}

Submission Info

Judge Result