Submission #534070

#	Time	Username	Problem	Language	Result	Execution time	Memory
534070		Cookie197	Intercastellar (JOI22_ho_t1)	C++14	100 / 100	76 ms	8632 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define pii pair<ll,ll> 
#define mp make_pair
#define endl "\n"
#define out(x) cout << #x << " = " << x << endl
#define outp(x) cout << #x << ".first = " << x.first << "  " << #x << ".second = " << x.second << endl
#pragma GCC optimize("Ofast")

int n,q;
ll arr[200005];
pii res[200005];
vector<ll> pre;
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    pre.push_back(0);
    for (int i=1;i<=n;i++) {
        cin>>arr[i];
        ll cnt=1, r=arr[i];
        while(1){
            if (r%2==1) break;
            r/=2; cnt*=2;
        }
        res[i] = mp(cnt, r);
        pre.push_back(pre.back()+cnt);
    }

    //for (int i=1;i<=n;i++) outp(res[i]), cout<<pre[i]<<endl;

    cin>>q;
    while(q--){
        ll x; cin>>x;
        int pos = lower_bound(pre.begin(),pre.end(),x) - pre.begin();
        //cout<<"#";
        cout<<res[pos].second<<endl;
    }
}

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