Submission #802877

#	Time	Username	Problem	Language	Result	Execution time	Memory
802877		devariaota	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	254 ms	10780 KiB

Main

#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 (stderr)

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

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40