Submission #1227710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227710		ProtonDecay314	Abracadabra (CEOI22_abracadabra)	C++20	10 / 100	483 ms	589824 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

void printv(const vi& a) {
    for(int v : a) cerr << v << " ";
    cerr << endl;
}

vi sh(const vi& a) {
    int n = a.size();

    vi res(n, 0);

    int hlfn = n >> 1;

    // [0, hlfn), [hlfn, n)

    int p1 = 0, p2 = hlfn;
    int resi = 0;

    while(p1 < hlfn && p2 < n) {
        if(a[p1] < a[p2]) {
            res[resi] = a[p1];
            p1++;
        } else {
            res[resi] = a[p2];
            p2++;
        }
        resi++;
    }

    while(p1 < hlfn) {
        res[resi] = a[p1];
        p1++;
        resi++;
    }

    while(p2 < n) {
        res[resi] = a[p2];
        p2++;
        resi++;
    }

    return res;
}

bool done(const vi& a) {
    int n = a.size();

    int hlfn = n >> 1;

    int maxhalf = *max_element(a.begin(), next(a.begin(), hlfn));

    return a[hlfn] > maxhalf;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;

    vi a(n, 0);

    for(int& v : a) cin >> v;

    vvi states;

    while(!done(a)) {
        states.pb(a);
        // printv(a);
        a = sh(a);

    }

    // printv(a);

    states.pb(a);

    while(q--) {
        int t, i;
        cin >> t >> i;
        i--;

        t = min(t, (int)(states.size()) - 1);

        cout << states[t][i] << "\n";
    }

    cout << flush;
}

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