oj.uz

Submission #682991

# Submission time Handle Problem Language Result Execution time Memory
682991 2023-01-17T12:34:24 Z nutella Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 336 ms 36908 KB 
#include <bits/stdc++.h>

using namespace std;

void riffle_shuffle(vector<int> &a) {
    vector<int> L(a.begin(), a.begin() + a.size() / 2);
    vector<int> R(a.begin() + a.size() / 2, a.end());

    int i = 0, j = 0;
    int n = a.size() / 2;

    while (i < n || j < n) {
        if (i != n && (j == n || L[i] < R[j])) {
            a[j + i] = L[i];
            i += 1;
        } else {
            a[j + i] = R[j];
            j += 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }

    vector<array<int, 3>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i][0] >> queries[i][1];
        queries[i][2] = i;
    }

    sort(queries.begin(), queries.end());

    vector<int> ans(q, -1);

    int pnt = 0;


    for (int _ = 0; ; ++_) {
        while (pnt < q && queries[pnt][0] == _) {
            ans[queries[pnt][2]] = a[queries[pnt][1] - 1];

            pnt += 1;
        }

        if (pnt == q) {
            break;
        }

        auto prv = a;

        riffle_shuffle(a);

        assert(_ <= n);
        
        auto count_mx = [&](int l, int r) {
            int mx = 0, cnt = 0;
            for (int i = l; i < r; ++i) {
                if (mx < a[i]) {
                    cnt += 1;
                    mx = a[i];
                }
            }
            return cnt;
        };
        
        if (_ >= 100) {
            assert(count_mx(0, n / 2) <= 100 && count_mx(n / 2, n) <= 100);
        }

        if (prv == a) {
            while (pnt < q) {
                ans[queries[pnt][2]] = a[queries[pnt][1] - 1];

                pnt += 1;
            }
            break;
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 263 ms 32160 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 336 ms 36908 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 71 ms 5936 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 263 ms 32160 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -