Submission #16726993

---

Source Code Expand

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

#define endl '\n'

const int max_n = 2e5 + 5;

int n, co;
int seen[max_n];
int a[max_n], b[max_n];
int A[max_n], B[max_n];
int L[max_n], R[max_n];

int r() {
	int x = (rand()%1000)*1000 + rand()%1000;
	return x%n;
}

bool FindMatch(int i) {
	for(int j = 0; j < 2000; j++) {
		int foo = r();
		if(a[i] != b[foo] && seen[foo] != co) {
			seen[foo] = co;
			if(R[foo] < 0 || FindMatch(R[foo])) {
				L[i] = foo;
				R[foo] = i;
				return true;
			}
		}
	}
	return false;
}

int BipartiteMatching() {
	memset(L, -1, sizeof L);
	memset(R, -1, sizeof R);
	for(int i=0; i<n; i++) {
		if(a[i] != b[i]) {
			L[i] = R[i] = i;
		}
	}
	for(int i = 0; i < n; i++) {
		if(L[i] == -1) {
			co = i + n;
			if(!FindMatch(i)) return 0;
		}
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	srand(time(NULL));

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

	for(int i=1; i<max_n; i++) {
		if(B[i] > n - A[i]) {
			cout << "No" << endl;
			return 0;
		}
	}

	reverse(b, b+n);
	if(BipartiteMatching()) {
		cout << "Yes" << endl;
		for(int i=0; i<n; i++) {
			cout << b[L[i]] << " ";
		}
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Submission Info

Judge Result