#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
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++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1259 ms |
12228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3050 ms |
13908 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3028 ms |
7512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1259 ms |
12228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
