oj.uz

Submission #968511

# Submission time Handle Problem Language Result Execution time Memory
968511 2024-04-23T14:04:22 Z anton Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 12032 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>


void shuffle(vector<int> &val){
    int k = val.size();
    vector<deque<int>> parts(2);
    for(int i =0; i<val.size()/2; i++){
        parts[0].push_back(val[i]);
        parts[1].push_back(val[i + val.size()/2]);
    }

    val.clear();
    while(val.size()<k){
        if(parts[0].size()==0){
            val.push_back(parts[1].front());
            parts[1].pop_front();
        }
        else if(parts[1].size()==0){
            val.push_back(parts[0].front());
            parts[0].pop_front();
        }
        else{
            if(parts[0].front()<parts[1].front()){
                val.push_back(parts[0].front());
                parts[0].pop_front();
            }
            else{
                val.push_back(parts[1].front());
                parts[1].pop_front();
            }
        }
    }
}

bool stable(vector<int>& r){
    int big = 0;
    for(int i = 0; i<r.size()/2; i++){
        big = max(big, r[i]);
    }
    return r[(r.size()/2)] > big;

}

vector<int> simulate(vector<int> v, int nb_steps){
    for(int i = 1; i<=nb_steps && !stable(v); i++){
        shuffle(v);
    }
    return v;
}
signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int n, q;
    cin>>n>>q;
    vector<int> v(n);

    for(int i = 0; i<n; i++){
        cin>>v[i];
    }


    if(n<=1000){

        vector<vector<int>> results;
        results.push_back(v);


        for(int i = 1; !stable(results.back()); i++){
            results.push_back(results.back());
            shuffle(results.back());
        }


        for(int i = 0;i<q; i++){
            int t, j;
            cin>>t>>j;
            if(t>=results.size()){
                cout<<results.back()[j-1]<<endl;
            }
            else{
                cout<<results[t][j-1]<<endl;
            }
        }
    }
    else{
        map<int, vector<int>> m;
        for(int i = 0; i<q; i++){
            int t, j;
            cin>>t>>j;
            if(m.find(t) == m.end()){
                m[t] = simulate(v, t);
            }
            cout<<m[t][j]<<endl;

        }
    }
}

Compilation message

Main.cpp: In function 'void shuffle(std::vector<long long int>&)':
Main.cpp:11:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i =0; i<val.size()/2; i++){
      |                   ~^~~~~~~~~~~~~
Main.cpp:17:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   17 |     while(val.size()<k){
      |           ~~~~~~~~~~^~
Main.cpp: In function 'bool stable(std::vector<long long int>&)':
Main.cpp:41:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0; i<r.size()/2; i++){
      |                    ~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:82:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if(t>=results.size()){
      |                ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1318 ms 12032 KB Output is correct
2 Correct 1229 ms 6208 KB Output is correct
3 Correct 1157 ms 7820 KB Output is correct
4 Correct 1137 ms 4292 KB Output is correct
5 Correct 1266 ms 6244 KB Output is correct
6 Correct 1140 ms 4788 KB Output is correct
7 Correct 1202 ms 5956 KB Output is correct
8 Correct 1159 ms 4568 KB Output is correct
9 Correct 1136 ms 4564 KB Output is correct
10 Correct 1174 ms 4952 KB Output is correct
11 Correct 1177 ms 4516 KB Output is correct
12 Correct 1151 ms 4152 KB Output is correct
13 Correct 1162 ms 4352 KB Output is correct
14 Correct 1163 ms 5228 KB Output is correct
15 Correct 1194 ms 4556 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1155 ms 4248 KB Output is correct
18 Correct 1165 ms 4160 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3038 ms 7268 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 3038 ms 4008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1318 ms 12032 KB Output is correct
2 Correct 1229 ms 6208 KB Output is correct
3 Correct 1157 ms 7820 KB Output is correct
4 Correct 1137 ms 4292 KB Output is correct
5 Correct 1266 ms 6244 KB Output is correct
6 Correct 1140 ms 4788 KB Output is correct
7 Correct 1202 ms 5956 KB Output is correct
8 Correct 1159 ms 4568 KB Output is correct
9 Correct 1136 ms 4564 KB Output is correct
10 Correct 1174 ms 4952 KB Output is correct
11 Correct 1177 ms 4516 KB Output is correct
12 Correct 1151 ms 4152 KB Output is correct
13 Correct 1162 ms 4352 KB Output is correct
14 Correct 1163 ms 5228 KB Output is correct
15 Correct 1194 ms 4556 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1155 ms 4248 KB Output is correct
18 Correct 1165 ms 4160 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3038 ms 7268 KB Time limit exceeded
22 Halted 0 ms 0 KB -