Submission #1196044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196044		finalpoi	Intercastellar (JOI22_ho_t1)	C++20	100 / 100	56 ms	7044 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
// using pr=pair<int,int>;
template<typename T>
using V=std::vector<T>;
template<typename T>
using VV=std::vector<std::vector<T>>;
#define nl '\n'
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(),x.end()
#define fr(a, b) for(const auto& a:b)
#define rep(a, b) for(int a=0; a<(b); a++)
#define coz(x) cerr<<(#x)<<": "<<(x)<<'\n'
#define cot(x, l, n) cerr<<(#x)<<": "; \
for(int i=l; i<l+n; i++) { cerr<<x[i]<<' '; } cerr<<'\n'

template <typename T, typename... Args>
inline void rd(T &x, Args&... args) {
    std::cin>>x;
    if constexpr(sizeof...(args)>0) (std::cin>>...>>args);
}

template <typename T, typename... Args>
inline void wt(const T &x, const Args &...args) {
    std::cout<<x;
    if constexpr(sizeof...(args)>0) ((std::cout<<' '<<args), ...);
    std::cout<<nl;
}

constexpr bool DEBUG=0;

template <typename T, typename... Args>
inline void bg(const T &x, const Args &...args) {
    if constexpr(!DEBUG) { return; }
    std::cerr<<x;
    if constexpr(sizeof...(args)>0) ((std::cerr<<' '<<args), ...);
    std::cerr<<nl;
}

const int N=2e5+6;
const int L=30;
const ll INF=1e18;

ll a[N];
ll b[N];
ll c[N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; rd(n);
    for(int i=1; i<=n; i++) { 
        rd(a[i]); 
        int l=0;
        while((l+1)<=L && a[i]%(1LL<<(l+1))==0) { l++; }
        c[i]=(1LL<<l);
        // bg(c[i]);
        b[i]=c[i]+b[i-1];
    }
    b[n+1]=INF;
    int q; rd(q);
    rep(_, q) {
        ll x; rd(x); // possibly out of bounds? (x>b[n])
        int l=1; int r=n;
        while(l<r) {
            int mid=(l+r)/2;
            // bg(l, mid, r, b[mid], x);
            if(b[mid]>=x) { r=mid; } 
            else { l=mid+1; }
        }
        wt(a[l]/c[l]);
    }
}

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