Submission #1074953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074953		ivaziva	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	378 ms	10836 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001

long long n,q;
long long a[MAXN],br[MAXN];
long long pref[MAXN];

int main()
{
    cin>>n;
    pref[0]=0;
    for (long long i=1;i<=n;i++)
    {
        cin>>a[i];long long x=a[i];
        while (x%2==0) {br[i]++;x/=2;}
        br[i]=(1<<br[i]);
        pref[i]=pref[i-1]+br[i];
    }
    pref[n+1]=LLONG_MAX;
    cin>>q;
    for (long long z=0;z<q;z++)
    {
        long long x;cin>>x;
        long long l=1,r=n+1;
        long long rez=0;
        while (l<=r)
        {
            long long mid=(l+r)/2;
            if (x>pref[mid-1] and x<=pref[mid]) {rez=mid;break;}
            else if (x>pref[mid]) l=mid+1;
            else r=mid-1;
        }
        cout<<a[rez]/br[rez]<<endl;
    }
}

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