Submission #508680

#	Time	Username	Problem	Language	Result	Execution time	Memory
508680		uncripted	Xor Sort (eJOI20_xorsort)	C++11	60 / 100	53 ms	1496 KiB

xorsort

#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])!=0){
					if((power[i]&ax[jj+1])==0){	
						k+=2;
						ax[jj+1]=(ax[jj]^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]^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)

xorsort.cpp: In function 'int main()':
xorsort.cpp:96:9: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   96 |    bool f=false;
      |         ^

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40