Submission #808444

#	Time	Username	Problem	Language	Result	Execution time	Memory
808444		devariaota	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	74 ms	9160 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define pq priority_queue
#define mp make_pair
#define str string
#define ll long long
#define ii pair<int, int>
#define pb push_back
#define MOD 1000000007

using namespace std;

// Feeling stuck? Scroll down for important points! Don't do nothing!
// Don't forget to see constraints, and to comment the cin t if unneccessary

const int N = 2e5+5;
ll a[N], pref[N];

void solve() {
  int n, q;
  cin >> n;
  for (int i=1; i<=n; i++) {
    ll cnt=1;
    
    cin >> a[i];
    if (a[i]%2 == 0) {
      while (a[i] % 2 == 0) {
        a[i]/=2;
        cnt*=2;
      }
    }
    
    pref[i]=pref[i-1] + cnt;
   }
   cin >> q;
   while (q--) {
     ll x, l=1, r=n, res=-1;
     cin >> x;
     while (l<=r) {
       ll mid=(l+r)/2;
       if (pref[mid] >= x) {
         res=a[mid];
         r=mid-1;
      }
      else l=mid+1;
    }
    cout << res << '\n';
  }
   
}

int main() {
  // your code goes here
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int t=1;
  // comment below if no test cases!
//  cout << "INPUT T: " << endl;
//  cin>>t;
  while(t--)
  {
      solve();
  }

  return 0;
}

// Remember to do easier subtasks for ALL problms
// in IO when stuck for too long
// Don't stare at the screen, nothing will come into your mind
// Actively try to view problem from different perspectives
// and or implement them quick if idea is doable

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