Submission #1176151

#TimeUsernameProblemLanguageResultExecution timeMemory
1176151yumemysteryIntercastellar (JOI22_ho_t1)C++20
100 / 100
52 ms5516 KiB
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;

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

    int n;
    vector<pii>num;
    cin >> n;
    num.resize(n);

    for (int i=0; i<n; i++) {
        ll castella;
        cin >> castella;
        ll cnt = 1;

        while (castella % 2 == 0) {
            castella/=2;
            cnt*=2;
        }

        if (i == 0) num[i] = {cnt,castella};
        else num[i] = {cnt+num[i-1].first,castella};
    }

    int q;
    cin >> q;

    while (q--) {
        ll target;
        cin >> target;

        int l = 0;
        int r = n-1;
        ll ans = num[0].second;

        while (l <= r) {
            int mid = l+(r-l)/2;

            if (num[mid].first == target) {
                ans = num[mid].second;
                break;
            }
            else if (num[mid].first < target) l = mid+1;
            else {
                r = mid-1;
                ans = num[mid].second;
            }
        }
        
        cout << ans << "\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...