Submission #1229624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229624		alexander707070	Abracadabra (CEOI22_abracadabra)	C++20	10 / 100	3094 ms	19908 KiB

Main

#include<bits/stdc++.h>

#define MAXN 1000007
using namespace std;

struct query{
    int t,pos,id;

    inline friend bool operator < (query fr,query sc){
        return fr.t<sc.t;
    }
}s[MAXN];

int n,qs,p[MAXN],q[MAXN];
int ans[MAXN];
bool ok;

bool transform(){
    int pt=n/2+1,m=0;
    for(int i=1;i<=n/2;i++){
        while(pt<=n and p[pt]<p[i]){
            m++; q[m]=p[pt]; pt++;
        }

        m++; q[m]=p[i];
    }

    while(pt<=n){
        m++; q[m]=p[pt]; pt++;
    }

    bool ok=false;
    for(int i=1;i<=n;i++){
        if(p[i]!=q[i])ok=true;
        p[i]=q[i];
    }

    return ok;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>qs;
    for(int i=1;i<=n;i++){
        cin>>p[i];
    }

    for(int i=1;i<=qs;i++){
        cin>>s[i].t>>s[i].pos;
        s[i].id=i;
    }

    sort(s+1,s+qs+1);

    ok=true;
    int curr=0;

    for(int i=1;i<=qs;i++){
        while(ok and curr<s[i].t){
            ok=transform(); curr++;
        }

        ans[s[i].id]=p[s[i].pos];
    }

    for(int i=1;i<=qs;i++){
        cout<<ans[i]<<"\n";
    }

    return 0;
}

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