oj.uz

Submission #739947

# Submission time Handle Problem Language Result Execution time Memory
739947 2023-05-11T17:49:23 Z PagodePaiva Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 67544 KB 
#include<bits/stdc++.h>
#define N 200010
// #define Q 1000010

using namespace std;

int n, q;
vector <pair <int, int>> query;
vector <int> v;
bool ver = false;

void shuff(){
    vector <int> aux;
    int l = 0, r = n/2;

    while(l < n/2 or r < n){
        if(l >= n/2){
            aux.push_back(v[r]);
            r++;
            continue;
        }

        if(r >= n){
            aux.push_back(v[l]);
            l++;
            continue;
        }

        if(v[l] < v[r]){
            aux.push_back(v[l]);
            l++;
        }

        else{
            aux.push_back(v[r]);
            r++;
        }
    }

    ver = true;

    for(int i = 0;i < n;i++){
        if(v[i] != aux[i]) ver = false;
    }

    v = aux;
    return;
}

int main(){
    cin >> n >> q;

    for(int i = 0;i < n;i++){
        int x;
        cin >> x;
        v.push_back(x);
    }

    map <pair <int, int>, int> m;

    for(int i = 0;i < q;i++){
        int a, b;
        cin >> a >> b;
        query.push_back({a, b});
        m[{a, b}] = i;
    }

    vector <pair <int, int>> ans = query;
    sort(query.begin(), query.end());
    query.push_back({1, 1});
    int con = 0;

    for(int i = 0;con < q;i++){
        if(ver == true){
            while(con < q){
                m[query[con]] = v[query[con].second-1];
                con++;
            }

            break;
        }
        while(query[con].first == i and con < q){
            m[query[con]] = v[query[con].second-1];
            con++;
        }
        shuff();        
    }

    for(auto x : ans){
        cout << m[x] << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2206 ms 67544 KB Output is correct
2 Correct 1738 ms 43364 KB Output is correct
3 Correct 1999 ms 52632 KB Output is correct
4 Correct 1030 ms 27224 KB Output is correct
5 Correct 1584 ms 38044 KB Output is correct
6 Correct 1304 ms 32172 KB Output is correct
7 Correct 1894 ms 39900 KB Output is correct
8 Correct 1238 ms 30936 KB Output is correct
9 Correct 1132 ms 28816 KB Output is correct
10 Correct 1046 ms 30020 KB Output is correct
11 Correct 1037 ms 30244 KB Output is correct
12 Correct 737 ms 25412 KB Output is correct
13 Correct 882 ms 27168 KB Output is correct
14 Correct 1374 ms 34164 KB Output is correct
15 Correct 891 ms 28008 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 632 ms 25584 KB Output is correct
18 Correct 676 ms 25404 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 300 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2206 ms 67544 KB Output is correct
2 Correct 1738 ms 43364 KB Output is correct
3 Correct 1999 ms 52632 KB Output is correct
4 Correct 1030 ms 27224 KB Output is correct
5 Correct 1584 ms 38044 KB Output is correct
6 Correct 1304 ms 32172 KB Output is correct
7 Correct 1894 ms 39900 KB Output is correct
8 Correct 1238 ms 30936 KB Output is correct
9 Correct 1132 ms 28816 KB Output is correct
10 Correct 1046 ms 30020 KB Output is correct
11 Correct 1037 ms 30244 KB Output is correct
12 Correct 737 ms 25412 KB Output is correct
13 Correct 882 ms 27168 KB Output is correct
14 Correct 1374 ms 34164 KB Output is correct
15 Correct 891 ms 28008 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 632 ms 25584 KB Output is correct
18 Correct 676 ms 25404 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 300 KB Output is correct
21 Execution timed out 3009 ms 41576 KB Time limit exceeded
22 Halted 0 ms 0 KB -