Submission #1309404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309404		sharanpai	Intercastellar (JOI22_ho_t1)	C++20	100 / 100	59 ms	6268 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int amtZeros(int num) {
    int res = 0;
    while (num > 0 && (num & 1) == 0) {
        ++res;
        num >>= 1;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> nums(N);
    for (int i = 0; i < N; ++i) cin >> nums[i];

    vector<pair<long long, int>> intervals; // {curLoc, num}
    long long curLoc = 1;
    for (int i = 0; i < N; ++i) {
        int endingZeros = amtZeros(nums[i]);
        if (endingZeros == 0) {
            intervals.push_back({ curLoc, nums[i] });
            ++curLoc;
        }
        else {
            int pow2 = pow(2, endingZeros);
            int num = nums[i] / pow2;
            intervals.push_back({ curLoc,num });
            curLoc += pow2;
        }
    }

    int Q; cin >> Q;
    for (int j = 0; j < Q; ++j) {
        long long Xj; cin >> Xj;
        int idx = lower_bound(intervals.begin(), intervals.end(), make_pair(Xj, -1)) - intervals.begin();
        if (idx == intervals.size() || intervals[idx].first > Xj) --idx;    // First value of intervals is curLoc = 1, Xj >= 1
        cout << intervals[idx].second << "\n";
    }
}

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