#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
int pas[40005][3];
pair<int,int> m[2000002][21];
int lpow[2000002];
int power[18];
int a[2000002];
int a1[2000002];
int n;
void pow2calc(int x){
power[1]=1;
for(int i=2; i<=x; i++){
power[i]=power[i-1]*2;
}
int cur=1;
int curi=1;
for(int i=1; i<=n; i++){
if(cur*2<=i){
cur*=2;
curi++;
lpow[i]=curi;
}else{
lpow[i]=curi;
}
}
}
void maxcalc(int x){
for(int i=1; i<=x; i++){
for(int j=1; j<=n; j++){
if(i==1){
m[j][1].f=a[j];
m[j][1].s=j;
continue;
}
if(j+power[i-1]<=n){
m[j][i].f=max(m[j][i-1].f, m[j+power[i-1]][i-1].f);
if(m[j][i].f==m[j][i-1].f){
m[j][i].s=m[j][i-1].s;
}else{
m[j][i].s=m[j+power[i-1]][i-1].s;
}
}
}
}
}
int maxrange(int l, int r){
int x=lpow[r-l+1];
int maxx=max(m[l][x].f, m[r-power[x]+1][x].f);
int index=-1;
if(maxx==m[l][x].f){
index=m[l][x].s;
}else{
index=m[r-power[x]+1][x].s;
}
return index;
}
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];
}
pow2calc(21);
maxcalc(21);
int lastsort=n;
while(lastsort!=1){
int maxi=maxrange(1, lastsort);
for(int i=lastsort-1; i>=1; i-- ){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
for(int i=maxi+1; i<=n; i++){
k++;
pas[k][1]=i;
pas[k][2]=i-1;
a1[i]=a1[i]^a1[i-1];
}
for(int i=maxi-2; i>=1; i--){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
lastsort--;
}
for(int i=n; i>=2; i--){
k++;
pas[k][1]=i-1;
pas[k][2]=i;
a1[i-1]=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 |
| 1 |
Incorrect |
1 ms |
204 KB |
Not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Not sorted |
| 2 |
Halted |
0 ms |
0 KB |
- |
