oj.uz

Submission #849187

# Submission time Handle Problem Language Result Execution time Memory
849187 2023-09-14T08:48:57 Z JakobZorz Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 34364 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 25792 KB Output is correct
2 Correct 408 ms 26888 KB Output is correct
3 Correct 347 ms 26144 KB Output is correct
4 Correct 551 ms 25216 KB Output is correct
5 Correct 588 ms 26756 KB Output is correct
6 Correct 540 ms 25508 KB Output is correct
7 Correct 574 ms 26928 KB Output is correct
8 Correct 543 ms 25524 KB Output is correct
9 Correct 556 ms 25348 KB Output is correct
10 Correct 550 ms 25704 KB Output is correct
11 Correct 606 ms 25604 KB Output is correct
12 Correct 522 ms 24452 KB Output is correct
13 Correct 553 ms 25472 KB Output is correct
14 Correct 585 ms 26396 KB Output is correct
15 Correct 575 ms 26312 KB Output is correct
16 Correct 12 ms 500 KB Output is correct
17 Correct 215 ms 24916 KB Output is correct
18 Correct 507 ms 24916 KB Output is correct
19 Correct 0 ms 360 KB Output is correct
20 Correct 0 ms 460 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3012 ms 34364 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 3045 ms 6964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 25792 KB Output is correct
2 Correct 408 ms 26888 KB Output is correct
3 Correct 347 ms 26144 KB Output is correct
4 Correct 551 ms 25216 KB Output is correct
5 Correct 588 ms 26756 KB Output is correct
6 Correct 540 ms 25508 KB Output is correct
7 Correct 574 ms 26928 KB Output is correct
8 Correct 543 ms 25524 KB Output is correct
9 Correct 556 ms 25348 KB Output is correct
10 Correct 550 ms 25704 KB Output is correct
11 Correct 606 ms 25604 KB Output is correct
12 Correct 522 ms 24452 KB Output is correct
13 Correct 553 ms 25472 KB Output is correct
14 Correct 585 ms 26396 KB Output is correct
15 Correct 575 ms 26312 KB Output is correct
16 Correct 12 ms 500 KB Output is correct
17 Correct 215 ms 24916 KB Output is correct
18 Correct 507 ms 24916 KB Output is correct
19 Correct 0 ms 360 KB Output is correct
20 Correct 0 ms 460 KB Output is correct
21 Execution timed out 3012 ms 34364 KB Time limit exceeded
22 Halted 0 ms 0 KB -