Submission #503574

#TimeUsernameProblemLanguageResultExecution timeMemory
503574uncriptedXor Sort (eJOI20_xorsort)C++11
0 / 100
1 ms332 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...