Submission #786075

#	Time	Username	Problem	Language	Result	Execution time	Memory
786075		larush	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	67 ms	10812 KiB

Main

#include <bits/stdc++.h>
#define debug(x) (cout<<'['<<(#x)<<':'<<(x)<<']'<<'\n')
using namespace std;
using ll=long long;

int main(){
    ios::sync_with_stdio(0), cin.tie(0);

    int n;
    cin>>n;
    vector<array<ll,2>> a(n);
    vector<ll> pf(n);
    ll s,p;
    for(int i=0; i<n; i++){
        cin>>s;
        p=1;
        while((s&1LL)==0){
            s>>=1;
            p<<=1;
        }
        a[i][0]=p, a[i][1]=s;
        pf[i]=(i ? pf[i-1]+a[i][0] : a[i][0]);
    }
    int q;
    cin>>q;
    while(q--){
        ll xi;
        cin>>xi;
        int l=0, r=n-1;
        while(r>l+1){
            int mid=(l+r)/2;
            if(pf[mid]>=xi) r=mid;
            else l=mid;
        }
        if(pf[l]>=xi) r=l;
        cout<<a[r][1]<<'\n';
    }
    return 0;
}

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