Submission #508534

#TimeUsernameProblemLanguageResultExecution timeMemory
508534uncriptedXor Sort (eJOI20_xorsort)C++11
60 / 100
62 ms1016 KiB
#include<bits/stdc++.h> using namespace std; #define ff first #define ss second int power[22]; int pas[40005][3]; int n; void pow2calc(int x){ power[1]=1; for(int i=2; i<=x; i++){ power[i]=power[i-1]*2; } } pair<int,int> aa[2000002]; int a1[2000002]; int a[2000005]; int main(){ int s; pow2calc(21); cin>>n; cin>>s; if(s==1){ int k=0; for(int i=1; i<=n; i++){ cin>>a[i]; a1[i]=a[i]; aa[i].ff=a[i]; aa[i].ss=i; } sort(aa+1, aa+n+1); int lastsort=n; while(lastsort!=1){ int maxi=aa[lastsort].ss; for(int i=1; i<=lastsort-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<=lastsort; 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]; } for(int i=1; i<=n; i++){ if(aa[i].ss>maxi){ aa[i].ss--; } } 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]<<" "; } } if(s==2){ int ax[n+1]; int k=0; for(int i=1; i<=n; i++){ cin>>ax[i]; } int last=n; for(int i=21; i>=1; i--){ int j=1; int z=(power[i]&ax[j]); while((power[i]&ax[j])==0 && j<=n){ j++; } if(j==n+1){ continue; } for(int jj=j; jj<last; jj++){ if((power[i]&ax[jj])!=0){ if((power[i]&ax[jj+1])==0){ k+=2; ax[jj+1]=(ax[jj]^a[jj+1]); ax[jj]=(ax[jj]^ax[jj+1]); pas[k-1][1]=jj+1; pas[k-1][2]=jj; pas[k][1]=jj; pas[k][2]=jj+1; }else{ k++; ax[jj]=(ax[jj]^ax[jj+1]); pas[k][1]=jj; pas[k][2]=jj+1; } } } last--; } cout<<k<<endl; for(int i=1; i<=k; i++){ cout<<pas[i][1]<<" "<<pas[i][2]<<endl; } for(int i=1; i<=n; i++){ // cout<<ax[i]<<" "; } } }

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:95:8: warning: unused variable 'z' [-Wunused-variable]
   95 |    int z=(power[i]&ax[j]);
      |        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...