Submission #968511

#	Time	Username	Problem	Language	Result	Execution time	Memory
968511		anton	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3038 ms	12032 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25