Submission #645379

#	Time	Username	Problem	Language	Result	Execution time	Memory
645379		1zaid1	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	99 ms	9364 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n';

const int M = 2e6+5, MOD = 1e9;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n;
    cin >> n;
    vector<int> v(n), p ={0};
    for (int &i:v) cin >> i;
    for (int &i:v) {
        p.push_back(p.back() + gcd(i, (1ll<<30)));
        i /= gcd(i, (1ll<<30));
    }

    int t;
    cin >> t;
    while (t--) {
        int x;
        cin >> x;

        cout << v[lower_bound(p.begin(), p.end(), x)-p.begin()-1] << endl;
    }

    return 0;
}

/*
4
14
9
8
12
6
2
3
5
7
11
13
*/

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