Submission #526379

#	Time	Username	Problem	Language	Result	Execution time	Memory
526379		mosiashvililuka	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	87 ms	10440 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[200009],X[200009],F[200009],g[200009],lef,rig,mid;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++){
		cin>>f[i];
	}
	for(i=a; i>=1; i--){
		c=f[i];d=0;
		while(c%2==0){
			c/=2;d++;
		}
		F[i]=c;g[i]=f[i]/c;
	}
	for(i=a; i>=1; i--){
		g[i]+=g[i+1];
	}
	cin>>tes;
	for(t=1; t<=tes; t++){
		cin>>c;c=g[1]-c+1;
		lef=0;rig=a+1;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			if(g[mid]<c){
				rig=mid;
			}else{
				lef=mid;
			}
		}
		cout<<F[lef]<<"\n";
	}
	return 0;
}

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