Submission #942066

#	Time	Username	Problem	Language	Result	Execution time	Memory
942066		Alexabcde1	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	276 ms	11132 KiB

Main

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
long long n,i,j,si[200005],cnt[200005],q,tmp;
long long a[200005];
long long f(long long x){
	if (x==1) return si[1];
	long long l=1; long long r=n;
	long long ans=0;
	while (l<=r){
		long long mid=(l+r)/2;
		if (cnt[mid]<x){
			l=mid+1;
		}
		else {
			ans=mid;
			r=mid-1;
		}
	}
	return si[ans];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for (i=1;i<=n;i++) {
		cin>>a[i];
		cnt[i]=1;
		si[i]=a[i];
		while (si[i]%2==0){
			si[i]/=2;
			cnt[i]*=2;
		}
		cnt[i]+=cnt[i-1];
	}
	cin>>q;
	while (q--){
		cin>>tmp;
		cout<<f(tmp)<<endl;
	}
}

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