제출 #1155395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155395		petkub	Intercastellar (JOI22_ho_t1)	C++20	100 / 100	50 ms	8516 KiB

Main

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1) Read input
    int N;
    cin >> N;

    // (value, count) for each group
    vector<pair<ll, ll>> pieces;
    pieces.reserve(N);  // To avoid multiple reallocations

    // Process each A: factor out powers of 2
    for(int i = 0; i < N; i++) {
        ll A;
        cin >> A;
        ll count = 1;
        while(A % 2 == 0) {
            A /= 2;
            count <<= 1;  // same as count *= 2
        }
        pieces.emplace_back(A, count);
    }

    // 2) Build prefix sums: prefix_sum[i] = total pieces up to (and including) pieces[i-1]
    //    prefix_sum[0] = 0 by definition
    vector<ll> prefix_sum(N + 1, 0LL);
    for(int i = 1; i <= N; i++){
        prefix_sum[i] = prefix_sum[i - 1] + pieces[i - 1].second;
    }

    // 3) Read queries
    int Q;
    cin >> Q;
    // Problem states queries are sorted in non-decreasing order (X_j <= X_{j+1})
    // so we can handle them in one pass
    vector<ll> queries(Q);
    for(int i = 0; i < Q; i++) {
        cin >> queries[i];
    }

    // 4) Two-pointer approach
    // i = index for prefix_sum (1..N)
    // we move through queries (j from 0..Q-1) in sorted order
    int i = 1;  // Start comparing from prefix_sum[1]
    for(int j = 0; j < Q; j++) {
        ll x = queries[j];

        // Move "i" forward until x <= prefix_sum[i]
        // That means the x-th piece is in the group i-1
        while(prefix_sum[i] < x) {
            i++;
        }
        // Now we know x-th piece belongs to pieces[i - 1]
        cout << pieces[i - 1].first << "\n";
    }

    return 0;
}

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