oj.uz

Submission #682985

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

        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 334 ms 27596 KB Output is correct
2 Correct 340 ms 27212 KB Output is correct
3 Correct 330 ms 26248 KB Output is correct
4 Correct 340 ms 25068 KB Output is correct
5 Correct 344 ms 26844 KB Output is correct
6 Correct 342 ms 25368 KB Output is correct
7 Correct 350 ms 26944 KB Output is correct
8 Correct 330 ms 25456 KB Output is correct
9 Correct 332 ms 25308 KB Output is correct
10 Correct 336 ms 25664 KB Output is correct
11 Correct 337 ms 25580 KB Output is correct
12 Correct 370 ms 24444 KB Output is correct
13 Correct 341 ms 25540 KB Output is correct
14 Correct 345 ms 26252 KB Output is correct
15 Correct 348 ms 26072 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 321 ms 24832 KB Output is correct
18 Correct 343 ms 24652 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3023 ms 33028 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 3077 ms 4904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 27596 KB Output is correct
2 Correct 340 ms 27212 KB Output is correct
3 Correct 330 ms 26248 KB Output is correct
4 Correct 340 ms 25068 KB Output is correct
5 Correct 344 ms 26844 KB Output is correct
6 Correct 342 ms 25368 KB Output is correct
7 Correct 350 ms 26944 KB Output is correct
8 Correct 330 ms 25456 KB Output is correct
9 Correct 332 ms 25308 KB Output is correct
10 Correct 336 ms 25664 KB Output is correct
11 Correct 337 ms 25580 KB Output is correct
12 Correct 370 ms 24444 KB Output is correct
13 Correct 341 ms 25540 KB Output is correct
14 Correct 345 ms 26252 KB Output is correct
15 Correct 348 ms 26072 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 321 ms 24832 KB Output is correct
18 Correct 343 ms 24652 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Execution timed out 3023 ms 33028 KB Time limit exceeded
22 Halted 0 ms 0 KB -