Submission #74109830

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
int 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]]++;
    }
    int K = 0;
    for (int i = 1; i <= M; ++i) {
        K = max(K, cnt[i]);
    }
    ll S = 1LL * M * K - N;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    for (int i = 1; i <= M; ++i) {
        pq.emplace(cnt[i], i);
    }
    vector<int> add;
    add.reserve(500010);
    for (ll i = 0; i < S; ++i) {
        auto [cur, v] = pq.top();
        pq.pop();
        add.push_back(v);
        pq.emplace(cur + 1, v);
    }
    int Q;
    cin >> Q;
    ll full = N + S;
    while (Q--) {
        ll X;
        cin >> X;
        if (X <= N) {
            cout << A[X - 1] << '\n';
        } else if (X <= full) {
            cout << add[X - N - 1] << '\n';
        } else {
            ll off = X - full - 1;
            cout << (off % M) + 1 << '\n';
        }
    }

    return 0;
}

Submission Info

Judge Result