Submission #1060611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060611		andrewp	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	59 ms	11384 KiB

Main

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout.tie(nullptr); cerr.tie(nullptr);

    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<pair<ll, ll>> data;
    data.push_back({0, 0});
    for (ll i = 0; i < n; i++) {
        ll p = a[i];
        while (!(p & 1)) {
            p >>= 1;
        }
        data.push_back({data.back().first + a[i] / p, p});
    }
    ll q;
    cin >> q;
    while (q--) {
        ll x;
        cin >> x;
        ll lb = 0, rb = data.size() - 1, ans = 0;
        while (lb <= rb) {
            int mb = lb + rb >> 1;
            if (data[mb].first >= x) {
                ans = mb;
                rb = mb - 1;
            } else {
                lb = mb + 1;
            }
        }
        cout << data[ans].second << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:38:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |             int mb = lb + rb >> 1;
      |                      ~~~^~~~

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