Submission #1325262

#TimeUsernameProblemLanguageResultExecution timeMemory
1325262bbldrizzyIntercastellar (JOI22_ho_t1)C++20
100 / 100
300 ms6952 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll MOD = 9223372036854775783;

ll exp(ll x, ll n, ll m) {
	assert(n >= 0);
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}

int main() {
    ll n; cin >> n;
    vector<ll> v(n);
    for (auto &it: v) cin >> it;
    vector<ll> pow2(n);
    vector<ll> acc(n);
    for (ll i = 0; i < n; i++) {
        ll t = v[i];
        while (t%2 == 0) {
            t /= 2;
            pow2[i]++;
        }
        acc[i] = t;
    }
    ll q; cin >> q;
    ll j = 0; 
    ll sm = 0;
    for (ll i = 0; i < q; i++) {
        ll x; cin >> x;
        while (sm < x) {
            sm += exp(2, pow2[j], MOD);
            j++;
        }
        cout << acc[j-1] << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...