Submission #526480

#	Time	Username	Problem	Language	Result	Execution time	Memory
526480		PurpleCrayon	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	77 ms	8928 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 2e5+10, MOD = 1e9+7;

void solve() {
    int n; cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first, a[i].second = 1;
        while (a[i].first % 2 == 0) {
            a[i].first /= 2;
            a[i].second *= 2;
        }
    }
    vector<ll> pre(n);
    for (int i = 0; i < n; i++) {
        pre[i] = a[i].second;
        if (i) pre[i] += pre[i-1];
    }
    int q; cin >> q;
    while (q--) {
        ll x; cin >> x;
        // find first thing >= x
        int p = std::lower_bound(pre.begin(), pre.end(), x) - pre.begin();
        cout << a[p].first << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    // cin >> T;
    while (T--) solve();
}

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