1303-D, *1900

Problem - D - Codeforces

 

 

풀이

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
map<ll, int> exponent;
 
void make_exponent(map<ll, int>& exponent)
{
    ll i = 1;
    ooop(bit, 30){
        exponent[i] = bit;
        i *= 2;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    make_exponent(exponent);
    while(t--){
        ll n, m;
        cin >> n >> m;
        vector<int> cnt(30);
        ll a, sum = 0;
        loop(i, m){
            cin >> a;
            sum += a;
            cnt[exponent[a]]++;
        }
 
        if(sum < n) cout << -1 << endl;
        else{
            int divide_cnt = 0;
            ll acc = 0;
            ooop(bit, 60){
                ll cur = (1LL<<bit);
                acc += cnt[bit]*cur;
                if((cur&n) == 0) continue;
                if(acc >= cur) acc -= cur;
                else{
                    int p = bit;
                    while(cnt[p] == 0) p++;
                    divide_cnt += p-bit;
                    cnt[p]--;
                    for(int b = p-1; b >= bit+1; b--) cnt[b]++;
                    acc += cur;
                }
            }
            cout << divide_cnt << endl;
        }
    }
 
    return 0;
}cs