Submission #849187

#	Time	Username	Problem	Language	Result	Execution time	Memory
849187		JakobZorz	Abracadabra (CEOI22_abracadabra)	C++14	10 / 100	3045 ms	34364 KiB

Main

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include<limits.h>
#include<math.h>
#include<iomanip>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<cstring>
#include<sstream>

#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second

struct Query{
    int i,t;
    int index,ans;
};


int n,q;
vector<pair<int,int>>deck;
Query queries[1000000];

void shuffle(){
    vector<pair<int,int>>d1,d2;
    
    int size1=0;
    for(auto i:deck){
        if(size1<n/2){
            if(size1+i.second-i.first>n/2){
                int mid=i.first+n/2-size1;
                size1=n/2;
                d1.push_back({i.first,mid});
                d2.push_back({mid,i.second});
            }else{
                d1.push_back({i.first,i.second});
                size1+=i.second-i.first;
            }
        }else{
            d2.push_back({i.first,i.second});
        }
    }
    
    d1.push_back({1000000,1000000});
    d2.push_back({1000000,1000000});
    int i1=0,i2=0;
    deck.clear();
    while(i1<d1.size()-1||i2<d2.size()-1){
        if(d1[i1].first>d2[i2].first){
            deck.push_back(d2[i2++]);
        }else if(d1[i1]<d2[i2]){
            deck.push_back(d1[i1++]);
        }
    }
}

int get(int idx){
    for(auto i:deck){
        idx-=i.second-i.first;
        if(idx<0){
            return i.second+idx;
        }
    }
    return -1;
}

bool cmp1(Query&a,Query&b){
    return a.t<b.t;
}

bool cmp2(Query&a,Query&b){
    return a.index<b.index;
}

vector<pair<int,int>>shorten(vector<pair<int,int>>&vec){
    vector<pair<int,int>>res;
    for(auto i:vec){
        if(!res.empty()&&res.back().second==i.first){
            res.back().second=i.second;
        }else{
            res.push_back(i);
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>n>>q;
    deck.resize(n);
    for(auto&i:deck){
        cin>>i.first;
        i.second=i.first+1;
    }
    deck=shorten(deck);
    
    for(int i=0;i<q;i++){
        cin>>queries[i].t>>queries[i].i;
        queries[i].i--;
        queries[i].index=i;
        queries[i].t=min(queries[i].t,n);
    }
    
    sort(queries,queries+q,cmp1);
    
    int cq=0;
    for(int cs=0;cs<=n;cs++){
        while(cq<q&&queries[cq].t==cs){
            queries[cq].ans=get(queries[cq].i);
            cq++;
        }
        shuffle();
        deck=shorten(deck);
    }
    
    sort(queries,queries+q,cmp2);
    
    for(int i=0;i<q;i++)
        cout<<queries[i].ans<<"\n";
    
    return 0;
}

/*
 
6 3
1 5 6 2 3 4
1 2
0 4
1 5
 
2
2
5
 
6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6
 
2
2
5
4
3
3
 
 */

Compilation message (stderr)

Main.cpp: In function 'void shuffle()':
Main.cpp:61:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(i1<d1.size()-1||i2<d2.size()-1){
      |           ~~^~~~~~~~~~~~
Main.cpp:61:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while(i1<d1.size()-1||i2<d2.size()-1){
      |                           ~~^~~~~~~~~~~~

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