Submission #75816018

---

Source Code Expand

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;

const array<int, 2> mod {(int)1e9 + 7, (int)1e9 + 9};
const int key = 39393939;

array<array<int, 1010101>, 2> P, H;
array<int, 1010101> cnt, B, ans;
int N, M, K;

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M;

	P[0][0] = P[1][0] = 1;
	for (int i = 1; i <= M; i++) {
		P[0][i] = P[0][i - 1] * key % mod[0];
		P[1][i] = P[1][i - 1] * key % mod[1];
	}

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

	for (int i = 1; i <= M; i++) {
		cin >> B[i];
		H[0][i] = (H[0][i - 1] + B[i] * P[0][i]) % mod[0];
		H[1][i] = (H[1][i - 1] + B[i] * P[1][i]) % mod[1];
	}

	for (int j = M - 1; ; j--) {
		if (H[0][j] * P[0][M - j] % mod[0] == (mod[0] + H[0][M] - H[0][M - j]) % mod[0]
			&& H[1][j] * P[1][M - j] % mod[1] == (mod[1] + H[1][M] - H[1][M - j]) % mod[1]) {
			
			K = j;

			break;
		}
	}

	for (int i = 0, j = 1; i < N; i++, j++) {
		if (j > M) {
			j = K + 1;
		}

		if (cnt[B[j]]--) {
			ans[i] = B[j];
		}

		else {
			for (int v = 0; v <= (int)1e6; v++) {
				for (int _ = 0; _ < cnt[v]; _++) {
					ans[i++] = v;
				}
			}

			break;
		}
	}

	for (int i = 0; i < N; i++) {
		cout << ans[i] << ' ';
	}
	cout << '\n';
	
	return 0;
}

Submission Info

Judge Result