Submission #1228854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228854		overwatch9	Abracadabra (CEOI22_abracadabra)	C++20	0 / 100	3094 ms	21324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
bool shuffle(vector <int> &nums) {
    bool done = true;
    int n = (int)nums.size();
    for (int i = 0; i < n/2; i++) {
        if (nums[i] > nums[n/2]) {
            done = false;
            break;
        }
    }
    if (done)
        return true;
    vector <int> new_arr(n);
    int p1 = 0, p2 = n/2;
    int i = 0;
    while (p1 < n/2 && p2 < n) {
        if (nums[p1] < nums[p2]) {
            new_arr[i++] = nums[p1++];
        } else {
            new_arr[i++] = nums[p2++];
        }
    }
    while (p1 < n/2)
        new_arr[i++] = nums[p1++];
    while (p2 < n)
        new_arr[i++] = nums[p2++];
    nums = new_arr;
    return false;
}
int main() {
    int n, q;
    cin >> n >> q;
    vector <int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    map <int, vector <pair <int, int>>> queries;
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        queries[a].push_back({b, i});
    }
    int lst = 0;
    bool done = false;
    vector <int> ans(q);
    for (auto i : queries) {
        if (!done) {
            for (int j = lst; j < i.first && !done; j++)
                done |= shuffle(nums);
        }
        for (auto j : i.second)
            ans[j.second] = nums[j.first-1];
    }
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

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