F. Equal multisets (greedy)

Codeforces Round #805 (Div. 3)

Problem

Let's say that both lengths are n Array of a and b. Every time you can be right b One of the two operations is performed by any number in ：（1） Multiply by two （2） Take down and divide by two .
The operation sequence is not limited , The number of times is unlimited , ask ： After some operation ,b Can you communicate with a identical .

Solution

1. First of all, you can put a Divide the number in by two , Until it becomes odd .
   reason ： If b Arrays can become a Array , that , It can also become a changed array . If it cannot be changed into a changed array , It means there is no solution .
2. here a There are odd numbers in the array , Then the operation is invalid . Only operation two is left .
3. because b The number in can only be reduced now , therefore , It should be from b The maximum number in starts to operate continuously .
   If it turns into 0 Can't with a One of the numbers is the same , So there's no solution .

Code

const int N = 2e5 + 5, M = 1e6 + 7;
int a[N], b[N];
map<int, int> mp;

int main()
{
    
	IOS;
	int T; cin >> T;
	while (T--)
	{
    
		mp.clear();
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		for (int i = 1; i <= n; i++) cin >> b[i];

		for (int i = 1; i <= n; i++)
		{
    
			while (a[i] % 2 == 0) a[i] /= 2;
			mp[a[i]]++;
		}

		sort(b + 1, b + n + 1, greater<int>());
		int f = 1;
		for (int i = 1; i <= n; i++)
		{
    
			while (b[i] && mp[b[i]] == 0)
				b[i] /= 2;
			if (b[i] == 0) f = 0;
			else mp[b[i]]--;
		}

		if (f) cout << "YES\n";
		else cout << "NO\n";
	}


	return 0;
}