Submission #1006208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006208		THXuan	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	60 ms	9304 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;
 
void solve()
{
	int n; cin >> n;
	vector<ll>a(n + 1),s(n + 1);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		if (a[i] % 2 == 1) {
			s[i] = s[i - 1] + 1;
		}
		else {
			for (int j = 1; j <= 30; j++) {
				ll num = (1 << j);
				if ((a[i] / num) % 2 == 1) {
					a[i] = a[i] / num;
					s[i] = s[i - 1] + num;
					break;
				}
			}
		}
	}
	int q; cin >> q;
	while (q--) {
		ll x; cin >> x;
		int lo = 1; int hi = n;
		while (lo < hi) {
			int mid = (lo + hi) / 2;
			if (s[mid] < x)lo = mid + 1;
			else hi = mid;
		}
		cout << a[lo] << "\n";
	}
}
 
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

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