#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(20);
maxcalc(20);
int lastsort=n;
while(lastsort!=1){
int maxi=maxrange(1, lastsort);
// cout<<maxi<<"maxi"<<endl;
a[maxi]=INT_MIN;
maxcalc(20);
for(int i=1; i<=lastsort-1; i++ ){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
// cout<<a1[i]<<" "<<a1[i+1]<<" "<<a1[i]<<"cri1"<<endl;
a1[i]=a1[i]^a1[i+1];
// cout<<a1[i]<<" "<<a1[i+1]<<" "<<a1[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]<<" "<<a1[i]<<"cri2"<<endl;
a1[i]=a1[i]^a1[i-1];
// cout<<a1[i]<<" "<<a1[i-1]<<" "<<a1[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]<<" "<<a1[i]<<"cri3"<<endl;
a1[i]=a1[i]^a1[i+1];
// cout<<a1[i]<<" "<<a1[i+1]<<" "<<a1[i]<<"crine3"<<endl;
}
// cout<<a1[lastsort]<<" cr "<<endl;
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 |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Not sorted |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
332 KB |
Not sorted |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Not sorted |
| 3 |
Halted |
0 ms |
0 KB |
- |
