# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
508648 | uncripted | Xor Sort (eJOI20_xorsort) | C++11 | 54 ms | 1600 KiB |
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 ff first
#define ss second
long long power[23];
long long pas[40005][3];
long long n;
void pow2calc(long long x){
power[1]=1;
for(long long i=2; i<=x; i++){
power[i]=power[i-1]*2;
}
}
pair<long long,long long> aa[2000002];
long long a1[2000002];
long long a[2000005];
int main(){
long long s;
pow2calc(22);
cin>>n;
cin>>s;
if(s==1){
long long k=0;
for(long long 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);
long long lastsort=n;
while(lastsort!=1){
long long maxi=aa[lastsort].ss;
for(long long i=1; i<=lastsort-1; i++ ){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
for(long long i=maxi+1; i<=lastsort; i++){
k++;
pas[k][1]=i;
pas[k][2]=i-1;
a1[i]=a1[i]^a1[i-1];
}
for(long long i=maxi-2; i>=1; i--){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
for(long long i=1; i<=n; i++){
if(aa[i].ss>maxi){
aa[i].ss--;
}
}
lastsort--;
}
for(long long 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(long long i=1; i<=k; i++){
cout<<pas[i][1]<<" "<<pas[i][2]<<endl;
}
cout<<endl;
for(long long i=1; i<=n; i++){
// cout<<a1[i]<<" ";
}
}
if(s==2){
long long ax[n+1];
long long k=0;
for(long long i=1; i<=n; i++){
cin>>ax[i];
}
long long last=n;
for(long long i=22; i>=1; i--){
bool f=false;
for(long long jj=1; jj<last; jj++){
f=true;
if((power[i]&ax[jj])){
if((power[i]&ax[jj+1])==0){
k+=2;
ax[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+1];
pas[k][1]=jj;
pas[k][2]=jj+1;
}
}
}
// last--;
}
cout<<k<<endl;
for(long long i=1; i<=k; i++){
cout<<pas[i][1]<<" "<<pas[i][2]<<endl;
}
for(long long i=1; i<=n; i++){
// cout<<ax[i]<<" ";
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |