Submission #47753733

---

Source Code Expand

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

const int MAX = 100007;
int A[MAX], B[MAX], ans;
map<int, priority_queue<int>, greater<int>> PQ, cand;

void Fail() {
	cout << -1;
	exit(0);
}

int GetGroup(int N) {
	if (!N) return 0;
	while (!(N & 1)) N >>= 1;
	return N;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) cin >> A[i];
	for (int i = 0; i < N; ++i) {
		cin >> B[i];
		PQ[GetGroup(B[i])].push(B[i]);
	}
	PQ[0] = {};

	for (int i = 0; i < N; ++i) {
		int n = A[i];
		while (n && PQ.find(GetGroup(n)) == PQ.end()) {
			while (!(n & 1)) {
				n >>= 1;
				ans++;
			}
			n >>= 1; ans++;
		}
		cand[GetGroup(n)].push(n);
	}

	unordered_map<int, int> diff;
	for (int i = 0; i < 31; ++i) diff[1LL << i] = i;

	for (auto& [n, CPQ] : PQ) {
		if (CPQ.size() > cand[n].size()) Fail();
		if (!n) break;
		while (!CPQ.empty()) {
			int a = CPQ.top(); CPQ.pop();
			int b = cand[n].top(); cand[n].pop();
			ans += diff[max(a, b) / min(a, b)];
		}
		while (!cand[n].empty()) {
			int a = cand[n].top(); cand[n].pop();
			while (a && (PQ.find(GetGroup(a)) == PQ.end() || PQ[GetGroup(a)].empty())) {
				while (!(a & 1)) {
					a >>= 1;
					ans++;
				}
				a >>= 1; ans++;
			}
			cand[GetGroup(a)].push(a);
		}
	}

	cout << ans;
	return 0;
}

Submission Info

Judge Result