Submission #784868

#	Time	Username	Problem	Language	Result	Execution time	Memory
784868		Arpenteur	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	62 ms	9284 KiB

Main

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using pli = pair<ll,int>;
const char el = '\n';

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  int n;
  cin >> n;
  vector<pli> PL; // position, length
  ll cur_pos = 1LL;
  for(int i=0, a, b, div; i<n; i++) {
    cin >> a;
    b = a;
    div = 1;
    while((b&1)==0) {
      b >>= 1;
      div <<= 1;
    }
    PL.push_back({cur_pos,a/div});
    cur_pos += div;
  }
  int q;
  cin >> q;
  int pos;
  ll x;
  while(q--) {
    cin >> x;
    auto f = [&] (pli& pl) { return x>=pl.first; };
    pos = distance(PL.begin(),
        partition_point(PL.begin(),PL.end(),f));
    pos--;
    cout << PL[pos].second << el;
  }
}

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