#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define INF (ll)(9e18)
#define int long long int
#define endl '\n'
using namespace std;
using pii=pair<int,int>;
pii tc (int n){
int i=1;
while (n%2==0){
i*=2;
n/=2;
}
return {i,n};
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(0);
int N,Q,temp;
vector<int> ans;
cin>>N;
int nb[N];
int ad[N];
for (int i=0;i<N;i++){
cin>>temp;
pii tempp=tc(temp);
if (i==0){
ad[i]=tempp.F;
nb[i]=tempp.S;
}
else{
ad[i]=ad[i-1]+tempp.F;
nb[i]=tempp.S;
}
}
cin>>Q;
for (int i=0;i<Q;i++){
cin>>temp;
int l=0;
int r=N-1;
int m=(l+r)/2;
while (l!=r and ad[m]!=temp){
if (ad[m]>temp){
r=m;
}
else{
l=m+1;
}
m=(l+r)/2;
}
ans.push_back(nb[m]);
}
for (int i=0;i<Q;i++){
cout<<ans[i]<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
31 ms |
4108 KB |
Output is correct |
| 4 |
Correct |
29 ms |
3512 KB |
Output is correct |
| 5 |
Correct |
49 ms |
5868 KB |
Output is correct |
| 6 |
Correct |
29 ms |
4292 KB |
Output is correct |
| 7 |
Correct |
48 ms |
5872 KB |
Output is correct |
| 8 |
Correct |
64 ms |
6024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
308 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
320 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
31 ms |
4108 KB |
Output is correct |
| 4 |
Correct |
29 ms |
3512 KB |
Output is correct |
| 5 |
Correct |
49 ms |
5868 KB |
Output is correct |
| 6 |
Correct |
29 ms |
4292 KB |
Output is correct |
| 7 |
Correct |
48 ms |
5872 KB |
Output is correct |
| 8 |
Correct |
64 ms |
6024 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
308 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
0 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
308 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
320 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
320 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
328 KB |
Output is correct |
| 23 |
Correct |
28 ms |
3408 KB |
Output is correct |
| 24 |
Correct |
35 ms |
4440 KB |
Output is correct |
| 25 |
Correct |
90 ms |
7436 KB |
Output is correct |
| 26 |
Correct |
45 ms |
4236 KB |
Output is correct |
| 27 |
Correct |
41 ms |
4196 KB |
Output is correct |
| 28 |
Correct |
88 ms |
6612 KB |
Output is correct |
| 29 |
Correct |
100 ms |
5884 KB |
Output is correct |
| 30 |
Correct |
42 ms |
3228 KB |
Output is correct |
| 31 |
Correct |
76 ms |
6296 KB |
Output is correct |
