Submission #1267641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267641		julia_08	Intercastellar (JOI22_ho_t1)	C++20	100 / 100	50 ms	5444 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 2e5 + 10;

ll a[MAXN], sum[MAXN];

int n;

int bs(ll x){

  int l = 1, r = n;

  while(l < r){
    int m = l + (r - l) / 2;
    if(sum[m] >= x) r = m;
    else l = m + 1;
  }

  int lsb = __builtin_ctz(a[r]);

  return (a[r] >> lsb);

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;

  for(int i=1; i<=n; i++) cin >> a[i];

  for(int i=1; i<=n; i++){

    int lsb = __builtin_ctz(a[i]);

    sum[i] = sum[i - 1] + (1LL << lsb);

  }

  int q; cin >> q;

  while(q--){

    ll x; cin >> x;
    cout << bs(x) << "\n";

  }
  

  return 0;
}

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