This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
int pas[40005][3];
int a[2000002];
pair<int,int> aa[2000002];
int a1[2000002];
int n;
int main(){
int s;
cin>>n;
cin>>s;
int k=0;
for(int i=1; i<=n; i++){
cin>>a[i];
a1[i]=a[i];
aa[i].f=a[i];
aa[i].s=i;
}
sort(aa+1, aa+n+1);
int lastsort=n;
while(lastsort!=1){
int maxi=aa[lastsort].s;
//cout<<lastsort;
// cout<<aa[3].s<<endl;
//cout<<maxi<<"maxi"<<endl;
for(int i=1; i<=lastsort-1; i++ ){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
// cout<<a1[i]<<" "<<a1[i+1]<<" "<<a[i]<<"cri1"<<endl;
a1[i]=a1[i]^a1[i+1];
// cout<<a1[i]<<" "<<a1[i+1]<<" "<<a[i]<<"crine1"<<endl;
}
for(int i=maxi+1; i<=lastsort; i++){
k++;
pas[k][1]=i;
pas[k][2]=i-1;
// cout<<a1[i]<<" "<<a1[i-1]<<" "<<a[i]<<"cri2"<<endl;
a1[i]=a1[i]^a1[i-1];
// cout<<a1[i]<<" "<<a1[i-1]<<" "<<a[i]<<"crine2"<<endl;
}
for(int i=maxi-2; i>=1; i--){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
// cout<<a1[i]<<" "<<a1[i+1]<<" "<<a[i]<<"cri3"<<endl;
a1[i]=a1[i]^a1[i+1];
// cout<<a1[i]<<" "<<a1[i+1]<<" "<<a[i]<<"crine3"<<endl;
}
// cout<<a1[lastsort]<<" cr "<<endl;
for(int i=1; i<=n; i++){
if(aa[i].s>maxi){
aa[i].s--;
}
// aa[maxi].s=lastsort;
}
lastsort--;
}
for(int i=n-1; i>=1; i--){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
cout<<k<<endl;
for(int i=1; i<=k; i++){
cout<<pas[i][1]<<" "<<pas[i][2]<<endl;
}
/*
cout<<endl;
for(int i=1; i<=n; i++){
cout<<a1[i]<<" ";
}
*/
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |