oj.uz

Submission #682987

# Submission time Handle Problem Language Result Execution time Memory
682987 2023-01-17T12:12:52 Z nutella Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 20784 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);

        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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20768 KB Output is correct
2 Correct 383 ms 20760 KB Output is correct
3 Correct 374 ms 19896 KB Output is correct
4 Correct 325 ms 19836 KB Output is correct
5 Correct 348 ms 20776 KB Output is correct
6 Correct 314 ms 19788 KB Output is correct
7 Correct 342 ms 20784 KB Output is correct
8 Correct 334 ms 19924 KB Output is correct
9 Correct 340 ms 19700 KB Output is correct
10 Correct 318 ms 20132 KB Output is correct
11 Correct 342 ms 20000 KB Output is correct
12 Correct 334 ms 19836 KB Output is correct
13 Correct 388 ms 20176 KB Output is correct
14 Correct 348 ms 20300 KB Output is correct
15 Correct 346 ms 20764 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 314 ms 20056 KB Output is correct
18 Correct 365 ms 19612 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 316 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 18444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 3124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 20768 KB Output is correct
2 Correct 383 ms 20760 KB Output is correct
3 Correct 374 ms 19896 KB Output is correct
4 Correct 325 ms 19836 KB Output is correct
5 Correct 348 ms 20776 KB Output is correct
6 Correct 314 ms 19788 KB Output is correct
7 Correct 342 ms 20784 KB Output is correct
8 Correct 334 ms 19924 KB Output is correct
9 Correct 340 ms 19700 KB Output is correct
10 Correct 318 ms 20132 KB Output is correct
11 Correct 342 ms 20000 KB Output is correct
12 Correct 334 ms 19836 KB Output is correct
13 Correct 388 ms 20176 KB Output is correct
14 Correct 348 ms 20300 KB Output is correct
15 Correct 346 ms 20764 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 314 ms 20056 KB Output is correct
18 Correct 365 ms 19612 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Execution timed out 3072 ms 18444 KB Time limit exceeded
22 Halted 0 ms 0 KB -