Submission #784424

#	Time	Username	Problem	Language	Result	Execution time	Memory
784424		gun_gan	Intercastellar (JOI22_ho_t1)	C++17	100 / 100	77 ms	8472 KiB

Main

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

const int MX = 2e5 + 5;

int N, Q;
int a[MX];

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0); 

      cin >> N;
      for(int i = 0; i < N; i++) cin >> a[i];

      reverse(a, a + N);

      vector<pair<ll, ll>> b;
      for(int i = 0; i < N; i++) {
            int k = a[i];
            while(!(k % 2)) k /= 2;

            b.push_back({a[i] / k, k});
      }

      reverse(b.begin(), b.end());

      ll sum = 0;
      for(auto &[cnt, x] : b) {
            sum += cnt;
            cnt = sum;
      }

      cin >> Q;
      for(int i = 1; i <= Q; i++) {
            ll x;
            cin >> x;

            int l = 0, r = (int) b.size() - 1, res = 0;
            while(l <= r) {
                  int mid = (l + r) >> 1;

                  if(b[mid].first >= x) {
                        res = mid, r = mid - 1;
                  } else {
                        l = mid + 1;
                  }
            }

            cout << b[res].second << '\n';
      }
      
}

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