Submission #638033

#	Time	Username	Problem	Language	Result	Execution time	Memory
638033		sofijavelkovska	Abracadabra (CEOI22_abracadabra)	C++14	10 / 100	3071 ms	31556 KiB

Main

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

int main()
{
    int n, q, shuffle, card, index, shuffles=0, t=0, i;
    cin >> n >> q;
    int a[n], answer[q]={0};
    tuple<int, int, int> queries[q];
    vector<int> left, right;
    for (i=0; i<n; i++)
        cin >> a[i];
    for (i=0; i<q; i++)
    {
        int shuffle, card;
        cin >> shuffle >> card;
        queries[i]={shuffle, card, i};

    }
    sort(queries, queries+q);
    while (true)
    {
        tie(shuffle, card, index)=queries[t];
        while (shuffle==shuffles)
        {
            answer[index]=a[card-1];
            t=t+1;
            if (t==q)
                break;
            tie(shuffle, card, index)=queries[t];
        }
        if (t==q)
            break;
        for (i=n/2-1; i>=0; i--)
            left.push_back(a[i]);
        for (i=n-1; i>=n/2; i--)
            right.push_back(a[i]);
        if (right[n/2-1]>*max_element(left.begin(), left.end()))
            break;
        i=0;
        while (!left.empty() && !right.empty())
        {
            if (left.back()<right.back())
            {
                a[i]=left.back();
                left.pop_back();
                i=i+1;
            }
            else
            {
                a[i]=right.back();
                right.pop_back();
                i=i+1;
            }
        }
        while (!left.empty())
        {
            a[i]=left.back();
            left.pop_back();
            i=i+1;
        }
        while (!right.empty())
        {
            a[i]=right.back();
            right.pop_back();
            i=i+1;
        }
        shuffles=shuffles+1;
    }
    while (t<q)
    {
        tie(shuffle, card, index)=queries[t];
        answer[index]=a[card-1];
        t=t+1;
    }
    for (i=0; i<q; i++)
        cout << answer[i] << endl;

    return 0;
}

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