Submission #74126455

---

Source Code Expand

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    vector<int> cnt(M + 1, 0);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[A[i]]++;
    }

    map<int, vector<int>> buckets;
    for (int v = 1; v <= M; v++) {
        buckets[cnt[v]].push_back(v);
    }
    for (auto& [c, vec] : buckets) {
        sort(vec.begin(), vec.end());
    }

    vector<int> seq = A;
    int total_ops = 0;
    bool balanced = false;

    while (!balanced && total_ops < 2000000) {
        auto it = buckets.begin();
        int cur_cnt = it->first;
        vector<int>& nums = it->second;
        int batch_size = nums.size();
        if (batch_size == M) {
            balanced = true;
            break;
        }
        for (int v : nums) {
            seq.push_back(v);
        }
        total_ops += batch_size;
        vector<int> moved = std::move(nums);
        buckets.erase(it);
        int next_cnt = cur_cnt + 1;
        auto& next_bucket = buckets[next_cnt];
        if (next_bucket.empty()) {
            next_bucket = std::move(moved);
        } else {
            vector<int> merged;
            merge(next_bucket.begin(), next_bucket.end(),
                  moved.begin(), moved.end(),
                  back_inserter(merged));
            next_bucket = std::move(merged);
        }
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int X;
        cin >> X;
        if (X <= N) {
            cout << A[X - 1] << '\n';
        } else if (X <= N + total_ops) {
            cout << seq[X - 1] << '\n';
        } else {
            int k = X - N;
            int offset = k - total_ops - 1;
            int ans = (offset % M) + 1;
            cout << ans << '\n';
        }
    }
    return 0;
}

Submission Info

Judge Result