Submission #839507

#	Time	Username	Problem	Language	Result	Execution time	Memory
839507		_Avocado_	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	64 ms	10748 KiB

Main

#include <bits/stdc++.h>
#define int int64_t
using namespace std;

vector<int>prefix;

int solve(int k, int l, int r){
	if(l == r) return l;
	
	int m = (l+r)/2;
	
	if(prefix[m] - prefix[l-1] < k){
		k -= (prefix[m] - prefix[l-1]);
		return solve(k, m+1, r);
	}
	return solve(k, l, m);
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	
	int n; cin>>n;
	
	vector<int>v(n);
	for(auto&u: v) cin>>u;
	
	vector<int>two(n);
	prefix.assign(n+1, 0);
	
	for(int i = 0; i<n; ++i){
		int a = v[i];
		int cur = 1;
		
		while(a % 2 == 0){
			a /= 2;
			cur *= 2;
		}
		
		two[i] = cur;
		prefix[i+1] = cur;
	}
	
	for(int i = 1; i<=n; ++i){
		prefix[i] += prefix[i-1];
	}
	
	int q; cin>>q;
	
	for(int i = 0; i<q; ++i){
		int a; cin>>a;
		int index = solve(a, 1, n);
		
		//cout<<"index "<<index<<endl;
		
		cout<<v[index-1]/two[index-1]<<'\n';
	}
	
	cout<<'\n';
}

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