Submission #725779

#	Time	Username	Problem	Language	Result	Execution time	Memory
725779		tengiz05	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3065 ms	33756 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
    }
    
    std::vector<std::vector<std::pair<int, int>>> Q(n + 1);
    std::vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        int t, p;
        std::cin >> t >> p;
        t = std::min(t, n);
        p--;
        Q[t].push_back({p, i});
    }
    
    for (int t = 0; t <= n; t++) {
        for (auto [p, id] : Q[t]) {
            ans[id] = a[p];
        }
        int l = 0, r = n / 2;
        std::vector<int> na;
        while (l < n / 2 && r < n) {
            if (a[l] < a[r]) {
                na.push_back(a[l++]);
            } else {
                na.push_back(a[r++]);
            }
        }
        while (l < n / 2) {
            na.push_back(a[l++]);
        }
        while (r < n) {
            na.push_back(a[r++]);
        }
        a = na;
    }
    
    for (int i = 0; i < q; i++) {
        std::cout << ans[i] + 1 << "\n";
    }
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25