Submission #534098

#	Time	Username	Problem	Language	Result	Execution time	Memory
534098		Wither	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	336 ms	7068 KiB

Main

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define Fors(i,a,b,s) for(int i=a;i<=b;i+=s)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define INF (ll)(9e18)
#define int long long int
using namespace std;
using ll=long long;
using pii=pair<int,int>;

pii tc (int n){
	int i=1;
	while (n%2==0){
		i*=2;
		n/=2;
	}
	return {i,n};
}





int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N,Q,temp;
	vector<int> ans;
	cin>>N;
	
	
	int nb[N];
	int ad[N];
	
	for (int i=0;i<N;i++){
		cin>>temp;
		pii tempp=tc(temp);
		
		if (i==0){
			ad[i]=tempp.F;
			nb[i]=tempp.S;
		}
		else{
			ad[i]=ad[i-1]+tempp.F;
			nb[i]=tempp.S;
		}
	}
	
	cin>>Q;
	for (int i=0;i<Q;i++){
		cin>>temp;
		int l=0;
		int r=N-1;
		int m=(l+r)/2;
		
		while (l!=r and ad[m]!=temp){
			if (ad[m]>temp){
				r=m;
			}
			else{
				l=m+1;
			}
			m=(l+r)/2;
		}
		ans.push_back(nb[m]);
	}
	for (int i=0;i<Q;i++){
		cout<<ans[i]<<endl;
	}
	
	
	
		
	
}

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