Submission #830409

#	Time	Username	Problem	Language	Result	Execution time	Memory
830409		PoonYaPat	Abracadabra (CEOI22_abracadabra)	C++14	10 / 100	3052 ms	29052 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> tu;

int cnt,n,q,ans[1000005];
vector<int> v;
bool same=false;
vector<tu> qq; //time, order of array, idx of answer

void shuffle() {
    vector<int> temp;
    int hlf=n/2;

    int l=0, r=hlf;
    while (l<hlf && r<n) {
        if (v[l]<v[r]) temp.push_back(v[l++]);
        else temp.push_back(v[r++]);
    }

    while (l<hlf) temp.push_back(v[l++]);
    while (r<n) temp.push_back(v[r++]);

    same=true;
    for (int i=0; i<n; ++i) if (temp[i]!=v[i]) same=false;
    swap(temp,v);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>q;
    for (int i=0; i<n; ++i) {
        int x; cin>>x;
        v.push_back(x);
    }

    for (int i=0; i<q; ++i) {
        int a,b; cin>>a>>b;
        qq.push_back(tu(a,b-1,i));
    }
    sort(qq.begin(),qq.end());

    int idx=0;

    while (idx<q && get<0>(qq[idx])==cnt) {
        ans[get<2>(qq[idx])]=v[get<1>(qq[idx])];
        ++idx;
    }

    while (!same) {
        shuffle();
        ++cnt;

        while (idx<q && get<0>(qq[idx])==cnt) {
            ans[get<2>(qq[idx])]=v[get<1>(qq[idx])];
            ++idx;
        }
        if (idx==q) break;
    }

    while (idx<q) {
        ans[get<2>(qq[idx])]=v[get<1>(qq[idx])];
        ++idx;
    }
    
    for (int i=0; i<q; ++i) cout<<ans[i]<<"\n";
}

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