Submission #739947

#	Time	Username	Problem	Language	Result	Execution time	Memory
739947		PagodePaiva	Abracadabra (CEOI22_abracadabra)	C++14	10 / 100	3060 ms	67544 KiB

Main

#include<bits/stdc++.h>
#define N 200010
// #define Q 1000010

using namespace std;

int n, q;
vector <pair <int, int>> query;
vector <int> v;
bool ver = false;

void shuff(){
    vector <int> aux;
    int l = 0, r = n/2;

    while(l < n/2 or r < n){
        if(l >= n/2){
            aux.push_back(v[r]);
            r++;
            continue;
        }

        if(r >= n){
            aux.push_back(v[l]);
            l++;
            continue;
        }

        if(v[l] < v[r]){
            aux.push_back(v[l]);
            l++;
        }

        else{
            aux.push_back(v[r]);
            r++;
        }
    }

    ver = true;

    for(int i = 0;i < n;i++){
        if(v[i] != aux[i]) ver = false;
    }

    v = aux;
    return;
}

int main(){
    cin >> n >> q;

    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }

    map <pair <int, int>, int> m;

    for(int i = 0;i < q;i++){
        int a, b;
        cin >> a >> b;
        query.push_back({a, b});
        m[{a, b}] = i;
    }

    vector <pair <int, int>> ans = query;
    sort(query.begin(), query.end());
    query.push_back({1, 1});
    int con = 0;

    for(int i = 0;con < q;i++){
        if(ver == true){
            while(con < q){
                m[query[con]] = v[query[con].second-1];
                con++;
            }

            break;
        }
        while(query[con].first == i and con < q){
            m[query[con]] = v[query[con].second-1];
            con++;
        }
        shuff();        
    }

    for(auto x : ans){
        cout << m[x] << "\n";
    }

    return 0;
}

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