oj.uz

Submission #1011204

# Submission time Handle Problem Language Result Execution time Memory
1011204 2024-06-30T05:31:09 Z Forested Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 32700 KB 
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r) - 1; i >= (i32)(l); --i)
#define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define LEN(x) (i32)size(x)
#define ALL(x) begin(x), end(x)
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

V<i32> riffle(V<i32> a) {
    V<i32> b;
    b.reserve(LEN(a));
    i32 l = 0, r = LEN(a) / 2;
    i32 lto = r, rto = LEN(a);
    while (LEN(b) < LEN(a)) {
        if (r == rto || (l < lto && a[l] < a[r])) {
            b.push_back(a[l++]);
        } else {
            b.push_back(a[r++]);
        }
    }
    return b;
}

int main() {
    i32 n, q;
    cin >> n >> q;
    V<i32> a(n);
    REP(i, n) {
        cin >> a[i];
    }
    V<i32> t(q), idx(q);
    REP(i, q) {
        cin >> t[i] >> idx[i];
        --idx[i];
    }
    map<i32, V<i32>> mt;
    REP(i, q) {
        mt[t[i]].push_back(i);
    }
    V<i32> ans(q, -1);
    i32 x = 0;
    while (true) {
        if (mt.count(x)) {
            for (i32 i : mt[x]) {
                ans[i] = a[idx[i]];
            }
        }
        V<i32> b = riffle(a);
        if (a == b) {
            break;
        }
        a = b;
        ++x;
    }
    REP(i, q) {
        if (ans[i] == -1) {
            ans[i] = a[idx[i]];
        }
    }
    REP(i, q) {
        cout << ans[i] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 30004 KB Output is correct
2 Correct 316 ms 28464 KB Output is correct
3 Correct 344 ms 27776 KB Output is correct
4 Correct 258 ms 26892 KB Output is correct
5 Correct 326 ms 29520 KB Output is correct
6 Correct 305 ms 28620 KB Output is correct
7 Correct 340 ms 30424 KB Output is correct
8 Correct 304 ms 27476 KB Output is correct
9 Correct 286 ms 27984 KB Output is correct
10 Correct 325 ms 26944 KB Output is correct
11 Correct 316 ms 27036 KB Output is correct
12 Correct 267 ms 25560 KB Output is correct
13 Correct 294 ms 26908 KB Output is correct
14 Correct 320 ms 28504 KB Output is correct
15 Correct 273 ms 27820 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 268 ms 26004 KB Output is correct
18 Correct 238 ms 26008 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3009 ms 32700 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 3050 ms 11716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 30004 KB Output is correct
2 Correct 316 ms 28464 KB Output is correct
3 Correct 344 ms 27776 KB Output is correct
4 Correct 258 ms 26892 KB Output is correct
5 Correct 326 ms 29520 KB Output is correct
6 Correct 305 ms 28620 KB Output is correct
7 Correct 340 ms 30424 KB Output is correct
8 Correct 304 ms 27476 KB Output is correct
9 Correct 286 ms 27984 KB Output is correct
10 Correct 325 ms 26944 KB Output is correct
11 Correct 316 ms 27036 KB Output is correct
12 Correct 267 ms 25560 KB Output is correct
13 Correct 294 ms 26908 KB Output is correct
14 Correct 320 ms 28504 KB Output is correct
15 Correct 273 ms 27820 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 268 ms 26004 KB Output is correct
18 Correct 238 ms 26008 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Execution timed out 3009 ms 32700 KB Time limit exceeded
22 Halted 0 ms 0 KB -