Submission #938630

#	Time	Username	Problem	Language	Result	Execution time	Memory
938630		vjudge1	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	463 ms	7748 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
vector<int>prefix;
int binarysearch(int i){
    int r=prefix.size();
    int l=0;
    while(l<r){
        if(l==r-1){
            if(prefix[r]<=i)return r;
            else return l;
        }
        int m=(l+r)/2;
        if(prefix[m]==i)return m;
        if(prefix[m]>i)
            r=m;
        else 
            l=m;
    }
}
pair<int,int> power(int i){
    int ans=1;
    while(i%ans==0){
        ans*=2;
    }
    ans/=2;
    i=i/ans;
    return make_pair(ans,i);
}
signed main(){
    int n,q;
    cin>>n;
    int sum=1;
    vector<int>v;
    prefix.push_back(sum);
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        pair<int,int>b=power(a);
        sum+=b.first;
        prefix.push_back(sum);
        v.push_back(b.second);
    }
    
    cin>>q;
    for(int i=0;i<q;i++){
        int b;
        cin>>b;
        int index=binarysearch(b);
        cout<<v[index]<<endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'long long int binarysearch(long long int)':
Main.cpp:21:1: warning: control reaches end of non-void function [-Wreturn-type]
   21 | }
      | ^

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