oj.uz

Submission #792463

# Submission time Handle Problem Language Result Execution time Memory
792463 2023-07-25T05:12:21 Z t6twotwo Abracadabra (CEOI22_abracadabra) C++17
40 / 100
 296 ms 45056 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void shuffle(vector<int> &a) {
    int n = a.size();
    vector<int> b;
    int j = n / 2;
    for (int i = 0; i < n / 2; i++) {
        while (j < n && a[j] < a[i]) {
            b.push_back(a[j++]);
        }
        b.push_back(a[i]);
    }
    for (int i = j; i < n; i++) {
        b.push_back(a[i]);
    }
    swap(a, b);
}
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;
    }
    if (N <= 1000 && 0) {
        vector<vector<int>> T;
        do {
            T.push_back(A);
            shuffle(A);
        } while (A != T.back());
        int M = T.size();
        while (Q--) {
            int t, i;
            cin >> t >> i;
            t = min(t, M - 1);
            i--;
            cout << T[t][i] << "\n";
        }
        return 0;
    }
    vector<int> q(Q);
    int t;
    for (auto &x : q) {
        cin >> t >> x;
        x--;
    }
    if (t == 0) {
        for (int x : q) {
            cout << A[x] << "\n";
        }
        return 0;
    }
    vector<int> f(N, N), stk;
    for (int i = N - 1; i >= 0; i--) {
        while (!stk.empty() && A[stk.back()] < A[i]) {
            stk.pop_back();
        }
        if (!stk.empty()) {
            f[i] = stk.back();
        }
        stk.push_back(i);
    }
    set<tuple<int, int, int>> s, s2;
    for (int i = 0; i < N; i = f[i]) {
        s.emplace(A[i], i, f[i]);
    }
    int T = N;
    while (t--) {
        while (1) {
            auto [_, l, r] = *prev(s.end());
            if (T - r + l < N / 2) {
                break;
            }
            T -= r - l;
            s2.insert(*prev(s.end()));
            s.erase(prev(s.end()));
        }
        if (T == N / 2) {
            break;
        }
        auto [v, l, r] = *prev(s.end());
        s.erase(prev(s.end()));
        int m = r - T + N / 2;
        s.emplace(v, l, m);
        for (int i = m; i < r; i = f[i]) {
            s.emplace(A[i], i, min(r, f[i]));
        }
    }
    s.insert(s2.begin(), s2.end());
    vector<int> B;
    for (auto [_, l, r] : s) {
        B.insert(B.end(), A.begin() + l, A.begin() + r);
    }
    for (int x : q) {
        cout << B[x] << "\n";
    }
    return 6/22;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 15860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 43496 KB Output is correct
2 Correct 296 ms 45056 KB Output is correct
3 Correct 191 ms 34108 KB Output is correct
4 Correct 162 ms 23868 KB Output is correct
5 Correct 191 ms 25312 KB Output is correct
6 Correct 202 ms 22712 KB Output is correct
7 Correct 195 ms 27996 KB Output is correct
8 Correct 189 ms 27216 KB Output is correct
9 Correct 182 ms 24512 KB Output is correct
10 Correct 190 ms 24752 KB Output is correct
11 Correct 149 ms 20412 KB Output is correct
12 Correct 147 ms 20856 KB Output is correct
13 Correct 206 ms 23740 KB Output is correct
14 Correct 194 ms 21360 KB Output is correct
15 Correct 190 ms 25152 KB Output is correct
16 Correct 17 ms 4116 KB Output is correct
17 Correct 166 ms 20080 KB Output is correct
18 Correct 157 ms 18116 KB Output is correct
19 Correct 47 ms 5932 KB Output is correct
20 Correct 55 ms 9412 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 11200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 15860 KB Output isn't correct
2 Halted 0 ms 0 KB -