Submission #938094

#	Time	Username	Problem	Language	Result	Execution time	Memory
938094		esomer	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	65 ms	7760 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	vector<int> A(N);
	for(auto &i : A) cin >> i;
	vector<long long> prefix(N, 0);
	for(int i = 0; i < N; i++){
		long long cnt = 1;
		while(A[i] % 2 == 0){
			cnt *= 2;
			A[i] /= 2;
		}
		if(i == 0) prefix[i] = cnt;
		else prefix[i] = prefix[i-1] + cnt;
	}
	int Q; cin >> Q;
	while(Q--){
		long long ind; cin >> ind;
		int lo = 0;
		int hi = N - 1;
		int bst = 0;
		while(lo <= hi){
			int mid = (lo + hi) / 2;
			if(prefix[mid] >= ind){
				bst = mid;
				hi = mid - 1;
			}else lo = mid + 1;
		}
		cout << A[bst] << "\n";
	}
}

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