Submission #968619

#	Time	Username	Problem	Language	Result	Execution time	Memory
968619		anton	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	3050 ms	13908 KiB

Main

#include<bits/stdc++.h>

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


void insert(vector<int>& v, vector<vector<int>> ads){
    int vid = 0;
    int adid = 0;
    vector<int> res;

    while(adid<ads.size() || vid<v.size()){
        if(adid==ads.size()){
            res.push_back(v[vid++]);
        }
        else if(vid==v.size()){
            for(auto e: ads[adid]){
                res.push_back(e);
            }
            adid++;
        }
        else{
            if(v[vid]<ads[adid][0]){
                res.push_back(v[vid++]);
            }
            else{
                for(auto e: ads[adid]){
                    res.push_back(e);
                }
                adid++;
            }
        }
    }
    swap(v, res);
}

int get_mciel(vector<int>& v){
    int val = 0, id= 0;
    for(int i = 0; i<v.size()/2; i++){
        if(v[i]>val){
            id=i;
            val = v[i];
        }
    }
    return id;
}

int get_suff(vector<int>& v, int big_left){
    int res= v.size();
    for(int i = v.size()/2; i<v.size(); i++){
        if(v[i]>big_left){
            return i;
        }
    }
    return v.size();
}

vector<vector<int>> sequences(vector<int>& v){

    vector<vector<int>> res;
    for(int i = 0; i<v.size();i++){
        if(res.size()==0 || v[i]>res.back()[0]){
            res.push_back(vector<int>(1, v[i]));
        }
        else{
            res.back().push_back(v[i]);
        }
    }

    auto cmp = [&](vector<int>&a, vector<int>& b){
        return a[0]<b[0];
    };
    sort(res.begin(), res.end(), cmp);
    return res;
}

vector<int> avance(vector<int> vals, int t){
    int static_suff = 0;
    
    while(vals[get_mciel(vals)]> vals[vals.size()/2] && t>0){
        int left_point= get_mciel(vals);
        static_suff = get_suff(vals, vals[left_point]);
        vector<int> suff_content;
        for(int i = static_suff; i<vals.size(); i++){
            suff_content.push_back(vals[i]);
            //cout<<"suf"<<vals[i]<<" ";
        }
        //cout<<endl;
        vector<int> actual;
        for(int i = 0; i<static_suff; i++){
            actual.push_back(vals[i]);
            //cout<<"cur "<<vals[i]<<" ";
        }
        //cout<<endl;
        vector<vector<int>> ads;
        int chunk_size = static_suff- (vals.size()/2);
        //cout<<"chunk size "<<chunk_size<<endl;
        while(t>0 && left_point<vals.size()/2){
            t--;
            vector<int> cur;
            left_point += chunk_size;
            for(int i = 0; i<chunk_size; i++){
                cur.push_back(actual[actual.size()-chunk_size+i]);
            }
            for(int i = 0; i<chunk_size; i++){
                actual.pop_back();
            }
            for(auto e: sequences(cur)){
                ads.push_back(e);
            }
        }
        insert(actual, ads);

        vals.clear();

        for(auto e: actual){
            vals.push_back(e);
        }
        for(auto e: suff_content){
            vals.push_back(e);
        }
        
    }
    return vals;
}
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];
    }

    vector<int> v2;

    /*for(int i = 0; i<10; i++){
        v2 = simulate(v, i+1);
        for(auto e: v2){
            cout<<e<<" ";
        }
        cout<<endl;
        v2 = avance(v, i+1);
        for(auto e: v2){
            cout<<e<<" ";
        }
        cout<<endl;
    }*/
    for(int i = 0; i<q; i++){
        int t, j;
        cin>>t>>j;
        j--;
        if(i==0){
            v2 =avance(v, t);
        }
        cout<<v2[j]<<endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void insert(std::vector<long long int>&, std::vector<std::vector<long long int> >)':
Main.cpp:13:15: 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]
   13 |     while(adid<ads.size() || vid<v.size()){
      |           ~~~~^~~~~~~~~~~
Main.cpp:13:33: 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]
   13 |     while(adid<ads.size() || vid<v.size()){
      |                              ~~~^~~~~~~~~
Main.cpp:14:16: 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]
   14 |         if(adid==ads.size()){
      |            ~~~~^~~~~~~~~~~~
Main.cpp:17: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]
   17 |         else if(vid==v.size()){
      |                 ~~~^~~~~~~~~~
Main.cpp: In function 'long long int get_mciel(std::vector<long long int>&)':
Main.cpp:40: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]
   40 |     for(int i = 0; i<v.size()/2; i++){
      |                    ~^~~~~~~~~~~
Main.cpp: In function 'long long int get_suff(std::vector<long long int>&, long long int)':
Main.cpp:51:30: 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]
   51 |     for(int i = v.size()/2; i<v.size(); i++){
      |                             ~^~~~~~~~~
Main.cpp:50:9: warning: unused variable 'res' [-Wunused-variable]
   50 |     int res= v.size();
      |         ^~~
Main.cpp: In function 'std::vector<std::vector<long long int> > sequences(std::vector<long long int>&)':
Main.cpp:62: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]
   62 |     for(int i = 0; i<v.size();i++){
      |                    ~^~~~~~~~~
Main.cpp: In function 'std::vector<long long int> avance(std::vector<long long int>, long long int)':
Main.cpp:85:35: 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]
   85 |         for(int i = static_suff; i<vals.size(); i++){
      |                                  ~^~~~~~~~~~~~
Main.cpp:99:32: 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]
   99 |         while(t>0 && left_point<vals.size()/2){
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~
Main.cpp: In function 'void shuffle(std::vector<long long int>&)':
Main.cpp:130: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]
  130 |     for(int i =0; i<val.size()/2; i++){
      |                   ~^~~~~~~~~~~~~
Main.cpp:136: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]
  136 |     while(val.size()<k){
      |           ~~~~~~~~~~^~
Main.cpp: In function 'bool stable(std::vector<long long int>&)':
Main.cpp:160: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]
  160 |     for(int i = 0; i<r.size()/2; i++){
      |                    ~^~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25