Submission #1179134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179134		acoatoitgs	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3097 ms	35592 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define ll long long
#define all(a) (a).begin(), (a).end()
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
void solve();

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    ll N, Q;
    cin >> N >> Q;

    vector<ll> V(N), swp(N);
    
    for(auto &i : V) cin >> i; 

    ll half = N/2;
    bool eq = 0;

    vector<array<ll,3>> query;
    for(ll q = 0; q < Q; q++)
    {
        ll x,y;
        cin >> x >> y, --y;
        query.push_back({x,y,q});
    }
    sort(all(query));

    auto sim = [&]() -> void
    {
        eq = 1;
        ll i = 0, j = half;
        ll ij = 0;
        while(i != half && j != N)
        {
            if(V[i] < V[j]) swp[ij++] = V[i++];
            else swp[ij++] = V[j++];

            if(swp[ij-1] != V[ij-1]) eq = 0;
        }

        while(i != half) 
        {
            if(V[i] != V[ij]) eq = 0;
            swp[ij++] = V[i++];
        }

        while(j != N) 
        {
            if(V[j] != V[ij]) eq = 0;
            swp[ij++] = V[j++];
        }

        swap(swp, V);
        return;
    };


    auto pr = [&](vector<ll> &V) -> void
    {
        for(int i = 0; i < half; i++) cout << V[i] << " ";
        cout << "  #  ";
        for(int i = half; i < N; i++) cout << V[i] << " ";

        cout << "\n";
    };

    ll it = 0;
    vector<ll> ans(Q);
    for(ll q = 0; q < Q; q++)
    {
        while(it < query[q][0] && !eq)
        {
            sim();
            it++;
        }
        ans[query[q][2]] = V[query[q][1]];
    }
    for(auto i : ans) cout << i << "\n";
}

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