oj.uz

Submission #802877

# Submission time Handle Problem Language Result Execution time Memory
802877 2023-08-02T15:27:39 Z devariaota Intercastellar (JOI22_ho_t1) C++17
100 / 100
 254 ms 10780 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define sec second
#define pb push_back
#define pqueue priority_queue
#define int long long
#define pii pair<int,int>
#define supercepat ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
//GA AC GA LAKI
using namespace std;
int tc,ans=0,n,in1,q;
int a[200005];
int pref[200005];
int b[200005];
void makepref(){
  for(int i=1;i<=n;i++){
    int temp=a[i]; pref[i]=1; b[i]=a[i];
    while(temp%2==0){
      pref[i]*=2;
      temp/=2;
      b[i]/=2;
    }
    pref[i]+=pref[i-1];
  }
}
main(){
  supercepat;
  cin>>n; for(int i=1;i<=n;i++) cin>>a[i];
  makepref();
  cin>>q;
  for(int i=1;i<=q;i++){
    cin>>in1;
    int l=1,r=n,mid;
    while(l<=r){
      mid=(l+r)/2;
//      cout<<mid<<" "<<pref[mid]<<endl;
      if(pref[mid]>=in1){
        r=mid-1;
        ans=mid;
      }
      else l=mid+1;
    }
    cout<<b[ans]<<endl;
  }
}

Compilation message

Main.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main(){
      | ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 52 ms 5496 KB Output is correct
4 Correct 165 ms 2688 KB Output is correct
5 Correct 228 ms 7052 KB Output is correct
6 Correct 113 ms 5356 KB Output is correct
7 Correct 226 ms 7120 KB Output is correct
8 Correct 224 ms 7216 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 336 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 52 ms 5496 KB Output is correct
4 Correct 165 ms 2688 KB Output is correct
5 Correct 228 ms 7052 KB Output is correct
6 Correct 113 ms 5356 KB Output is correct
7 Correct 226 ms 7120 KB Output is correct
8 Correct 224 ms 7216 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 135 ms 3224 KB Output is correct
24 Correct 110 ms 6288 KB Output is correct
25 Correct 250 ms 10312 KB Output is correct
26 Correct 138 ms 6472 KB Output is correct
27 Correct 115 ms 6636 KB Output is correct
28 Correct 247 ms 10780 KB Output is correct
29 Correct 253 ms 10188 KB Output is correct
30 Correct 174 ms 3948 KB Output is correct
31 Correct 254 ms 10676 KB Output is correct