?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
185619146 |
Practice: Perennial_Coder |
1744D - 23 | C++20 (GCC 11-64) | Time limit exceeded on test 2 | 2000 ms | 16 KB | 2022-12-17 14:43:31 | 2022-12-17 14:43:31 |
#include<bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL); #define FILE_READ_IN freopen("input.txt","r",stdin); #define FILE_READ_OUT freopen("output.txt","w",stdout); #define deb(x) cout<<#x<<":= "<<x<<"\n"; #define MOD 1000000007 #define amax(x,y) x=max(x,y); #define amin(x,y) x=min(x,y); #define all(T) T.begin(),T.end() using namespace std; typedef int64_t ll; typedef long double ld; const int N = 1e5; void solve() { int n; cin >> n; vector<int> a(n); ll product = 1; for(int i=0;i<n;i++) { cin >> a[i]; product*= a[i]; } // deb(product) int req = n; while(product%2==0) product/=2,req--; // deb(req) // now we require req no. of 2s to make product divisible by 2^n vector<int> power2(n); for(int i=1;i<=n;i++) { int p = 0; int curr = i; while(curr%2==0) curr/=2,p++; power2[i-1]=p; } sort(power2.rbegin(),power2.rend()); int curr = 0; while(curr < n && req > 0) { req-=power2[curr]; curr++; } cout << ((req == 0) ? curr : -1) << "\n"; } int main() { FAST #ifndef ONLINE_JUDGE FILE_READ_IN FILE_READ_OUT #endif int t=1; cin>>t; while (t--) { solve(); } return 0; }
?
?
?
?