oj.uz

Submission #831656

# Submission time Handle Problem Language Result Execution time Memory
831656 2023-08-20T11:58:54 Z QwertyPi Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 31760 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> shuffle(vector<int> a){
    int n = a.size();
    vector<int> a1(a.begin(), a.begin() + n / 2), a2(a.begin() + n / 2, a.end());
    a1.push_back(1 << 30); a2.push_back(1 << 30);
    int l = 0, r = 0;
    vector<int> b;
    for(int i = 0; i < n; i++){
        if(a1[l] < a2[r]) b.push_back(a1[l++]);
        else b.push_back(a2[r++]);
    }
    return b;
}

const int MAXN = 2e5 + 11;
const int MAXQ = 1e6 + 11;
int ans[MAXQ];

struct query{
    int t, i, id;
    bool operator< (const query& o) const {
        return t < o.t;
    }
};

int32_t main(){
    int n, q; cin >> n >> q;
    vector<int> a1, a2;
    for(int i = 0; i < n; i++){
        int v; cin >> v; a1.push_back(v);
    }

    vector<query> Q;
    for(int id = 0; id < q; id++){
        int t, i; cin >> t >> i; Q.push_back({t, i, id});
    }
    sort(Q.begin(), Q.end());

    int ct = 0; bool fixed = false;
    for(auto q : Q){
        while(ct < q.t && !fixed) { a2 = shuffle(a1); if(a1 == a2) fixed = true; a1 = a2; ct++; }
        ans[q.id] = a1[q.i - 1];
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 27644 KB Output is correct
2 Correct 405 ms 27352 KB Output is correct
3 Correct 399 ms 26464 KB Output is correct
4 Correct 372 ms 25104 KB Output is correct
5 Correct 398 ms 26936 KB Output is correct
6 Correct 378 ms 25424 KB Output is correct
7 Correct 455 ms 27068 KB Output is correct
8 Correct 389 ms 25560 KB Output is correct
9 Correct 373 ms 25264 KB Output is correct
10 Correct 376 ms 25696 KB Output is correct
11 Correct 371 ms 25628 KB Output is correct
12 Correct 343 ms 24528 KB Output is correct
13 Correct 362 ms 25464 KB Output is correct
14 Correct 390 ms 26260 KB Output is correct
15 Correct 379 ms 26260 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 330 ms 24888 KB Output is correct
18 Correct 335 ms 24768 KB Output is correct
19 Correct 0 ms 312 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3022 ms 31760 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 3054 ms 6220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 27644 KB Output is correct
2 Correct 405 ms 27352 KB Output is correct
3 Correct 399 ms 26464 KB Output is correct
4 Correct 372 ms 25104 KB Output is correct
5 Correct 398 ms 26936 KB Output is correct
6 Correct 378 ms 25424 KB Output is correct
7 Correct 455 ms 27068 KB Output is correct
8 Correct 389 ms 25560 KB Output is correct
9 Correct 373 ms 25264 KB Output is correct
10 Correct 376 ms 25696 KB Output is correct
11 Correct 371 ms 25628 KB Output is correct
12 Correct 343 ms 24528 KB Output is correct
13 Correct 362 ms 25464 KB Output is correct
14 Correct 390 ms 26260 KB Output is correct
15 Correct 379 ms 26260 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 330 ms 24888 KB Output is correct
18 Correct 335 ms 24768 KB Output is correct
19 Correct 0 ms 312 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Execution timed out 3022 ms 31760 KB Time limit exceeded
22 Halted 0 ms 0 KB -