oj.uz

Submission #772672

# Submission time Handle Problem Language Result Execution time Memory
772672 2023-07-04T10:14:39 Z doowey Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 31404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
const int M = (int)1e6 + 10;

vector<int> shuffle(vector<int> P){
    queue<int> A, B;
    for(int i = 0 ; i < P.size(); i ++ ){
        if(i < P.size() / 2) A.push(P[i]);
        else B.push(P[i]);
    }
    vector<int> nex;
    while(!A.empty() || !B.empty()){
        if(A.empty()){
            nex.push_back(B.front());
            B.pop();
        }
        else if(B.empty()){
            nex.push_back(A.front());
            A.pop();
        }
        else {
            if(A.front() < B.front()){
                nex.push_back(A.front());
                A.pop();
            }
            else{
                nex.push_back(B.front());
                B.pop();
            }
        }
    }
    return nex;
}

vector<pii> qq[N]; // {index, idx}
int res[M];

int main(){
    fastIO;
    //freopen("test.txt", "r", stdin);
    int n, q;
    cin >> n >> q;
    vector<int> P(n);
    for(int i = 0 ; i < n; i ++ ){
        cin >> P[i];
    }
    int t, id;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> t >> id;
        t=min(t,n);
        qq[t].push_back(mp(id, iq));
    }
    for(int i = 0 ; i <= n; i ++ ){
        if(i) P = shuffle(P);
        for(auto x : qq[i]){
            res[x.se] = P[x.fi-1];
        }
    }
    for(int iq = 1; iq <= q; iq ++ ){
        cout << res[iq] << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'std::vector<int> shuffle(std::vector<int>)':
Main.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0 ; i < P.size(); i ++ ){
      |                     ~~^~~~~~~~~~
Main.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |         if(i < P.size() / 2) A.push(P[i]);
      |            ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 23356 KB Output is correct
2 Correct 163 ms 29340 KB Output is correct
3 Correct 157 ms 28704 KB Output is correct
4 Correct 164 ms 27404 KB Output is correct
5 Correct 184 ms 30980 KB Output is correct
6 Correct 152 ms 30436 KB Output is correct
7 Correct 168 ms 31404 KB Output is correct
8 Correct 150 ms 29208 KB Output is correct
9 Correct 151 ms 27872 KB Output is correct
10 Correct 152 ms 27776 KB Output is correct
11 Correct 157 ms 28220 KB Output is correct
12 Correct 161 ms 25680 KB Output is correct
13 Correct 155 ms 26988 KB Output is correct
14 Correct 155 ms 29692 KB Output is correct
15 Correct 181 ms 27520 KB Output is correct
16 Correct 6 ms 4948 KB Output is correct
17 Correct 151 ms 25832 KB Output is correct
18 Correct 165 ms 25892 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3035 ms 18476 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 3071 ms 10360 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 23356 KB Output is correct
2 Correct 163 ms 29340 KB Output is correct
3 Correct 157 ms 28704 KB Output is correct
4 Correct 164 ms 27404 KB Output is correct
5 Correct 184 ms 30980 KB Output is correct
6 Correct 152 ms 30436 KB Output is correct
7 Correct 168 ms 31404 KB Output is correct
8 Correct 150 ms 29208 KB Output is correct
9 Correct 151 ms 27872 KB Output is correct
10 Correct 152 ms 27776 KB Output is correct
11 Correct 157 ms 28220 KB Output is correct
12 Correct 161 ms 25680 KB Output is correct
13 Correct 155 ms 26988 KB Output is correct
14 Correct 155 ms 29692 KB Output is correct
15 Correct 181 ms 27520 KB Output is correct
16 Correct 6 ms 4948 KB Output is correct
17 Correct 151 ms 25832 KB Output is correct
18 Correct 165 ms 25892 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Execution timed out 3035 ms 18476 KB Time limit exceeded
22 Halted 0 ms 0 KB -