#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, q;
vi arr, two;
int main(){
cin>>n;
arr.resize(n);
two.resize(n);
for(int i = 0; i < n; i++) cin>>arr[i];
vector<pll> segments;
vl val;
ll last = -1;
// reverse(arr.begin(), arr.end());
for(int i = 0; i < n; i++){
ll x = arr[i];
two[i]=1;
while(x%2 == 0){
two[i]*=2;
x/=2;
}
segments.pb(mp(last+1, last + two[i]));
val.pb(x);
last += two[i];
}
ll pref[n];
pref[0] = segments[0].second + 1;
for(int i = 1; i < n; i++)
pref[i] = pref[i-1] + segments[i].second - segments[i].first+1;
int q;
cin>>q;
while(q--)
{
ll x;
cin>>x;
int l = 0, r = n-1, pos;
while(l <= r){
int mid = l + (r-l)/2;
if(pref[mid] >= x){
pos = mid;
r = mid - 1;
}
else
l = mid+1;
}
cout<<val[pos]<<endl;
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:52:16: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
52 | cout<<val[pos]<<endl;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
89 ms |
9932 KB |
Output is correct |
4 |
Correct |
242 ms |
2924 KB |
Output is correct |
5 |
Correct |
338 ms |
10492 KB |
Output is correct |
6 |
Correct |
177 ms |
9128 KB |
Output is correct |
7 |
Correct |
332 ms |
10548 KB |
Output is correct |
8 |
Correct |
359 ms |
10468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
316 KB |
Output is correct |
12 |
Correct |
3 ms |
312 KB |
Output is correct |
13 |
Correct |
2 ms |
340 KB |
Output is correct |
14 |
Correct |
3 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
89 ms |
9932 KB |
Output is correct |
4 |
Correct |
242 ms |
2924 KB |
Output is correct |
5 |
Correct |
338 ms |
10492 KB |
Output is correct |
6 |
Correct |
177 ms |
9128 KB |
Output is correct |
7 |
Correct |
332 ms |
10548 KB |
Output is correct |
8 |
Correct |
359 ms |
10468 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
3 ms |
316 KB |
Output is correct |
20 |
Correct |
3 ms |
312 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
3 ms |
340 KB |
Output is correct |
23 |
Correct |
203 ms |
3996 KB |
Output is correct |
24 |
Correct |
189 ms |
10504 KB |
Output is correct |
25 |
Correct |
409 ms |
15520 KB |
Output is correct |
26 |
Correct |
239 ms |
9580 KB |
Output is correct |
27 |
Correct |
209 ms |
10948 KB |
Output is correct |
28 |
Correct |
446 ms |
15972 KB |
Output is correct |
29 |
Correct |
429 ms |
15556 KB |
Output is correct |
30 |
Correct |
275 ms |
4572 KB |
Output is correct |
31 |
Correct |
437 ms |
15908 KB |
Output is correct |