Submission #1179666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179666		Szymon_Pilipczuk	Intercastellar (JOI22_ho_t1)	C++20	100 / 100	91 ms	5520 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define ll long long
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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;
    }
    for(int i = 0;i<n;i++)
    {
        while(a[i].first%2 == 0)
        {
            a[i].first/=2;
            a[i].second*=2;
        }
    }
    vector<ll> s(n+1);
    s[0] = 0;
    for(int i = 0;i<n;i++)
    {
        s[i+1] = s[i]+a[i].second;
    }
    int q;
    cin>>q;
    for(int i = 0;i<q;i++)
    {
        ll x;
        cin>>x;
        int l = 0;
        int r = n+1;
        while(l+1 < r)
        {
            int mid = (l+r)/2;
            if(s[mid] >= x)
            {
                r = mid;
            }
            else
            {
                l = mid;
            }
        }
        cout<<a[l].st<<"\n";
    }
}

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