Submission #706502

#	Time	Username	Problem	Language	Result	Execution time	Memory
706502		xuliu	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	76 ms	12432 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define debug if(0)

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin>>n;
	vector<ll> a(n), pref(n);
	vector<pair<ll, ll>> t;
	for(int i=0; i<n; i++) {
		cin>>a[i];
		int cnt = 1, left = a[i];
		while(left%2 == 0) {
			cnt<<=1;
			left>>=1;
		}
		t.push_back({left, cnt});
		if(i == 0) pref[i] = cnt;
		else pref[i] = pref[i-1]+cnt;
	}
	int q; cin>>q;
	while(q--) {
		ll x; cin>>x;
		int lo = 0, hi = n-1;
		while(lo < hi) {
			int m = (lo+hi)/2;
			if(pref[m] < x) lo = m+1;
			else hi = m;
		}
		if(lo < 0) lo = 0;
		cout<<t[lo].first<<"\n";
	}
}

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