Submission #508487

#	Time	Username	Problem	Language	Result	Execution time	Memory
508487		uncripted	Xor Sort (eJOI20_xorsort)	C++11	0 / 100	1 ms	304 KiB

xorsort

#include<bits/stdc++.h>
using namespace std;
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;
	}



}
int k=0;
int a[2000005];
int main(){
int s;

pow2calc(21);
cin>>n;
cin>>s;
int a1[n+1];
for(int i=1; i<=n; i++){
	cin>>a[i];
	
}//cout<<"a";
int last=n;

	for(int i=21; i>=1; i--){
		int j=1;
	//	cout<<"a";
		bool f=false;
		int z=(power[i]&a[j]);
		//cout<<z<<endl;
		while((power[i]&a[j])==0 && j<=n){
		//	cout<<"as";
		//cout<<power[i]<<" "<<a[j]<<endl;
			j++;
		
			//	cout<<"ni";
			
	
		}		
		if(j==n+1){
		continue;
		}
//	cout<<"y";
		for(int jj=j; jj<last; jj++){
		//cout<<"a";
			if((power[i]&a[jj])!=0){
			//	cout<<power[i]<<" "<<a[jj+1]<<((power[i])&(a[jj+1]))<<"jig"<<endl;
			
				if((power[i]&a[jj+1])==0){	
					k+=2;
					a[jj+1]=(a[jj]^a[jj+1]);
					a[jj]=(a[jj]^a[jj+1]);
			//		cout<<jj+1<<" "<<jj<<" r1"<<endl;
				//	cout<<jj<<" "<<jj+1<<" r1"<<endl;
					pas[k-1][1]=jj+1;
					pas[k-1][2]=jj;
					pas[k][1]=jj;
					pas[k][2]=jj+1;
				}else{
					k++;
					a[jj]=(a[jj]^a[jj+1]);
				//	cout<<jj<<" "<<jj+1<<" r2"<<endl;
					pas[k][1]=jj;
					pas[k][2]=jj+1;
				}
			//	cout<<"ching chong";
			}
		}
		last--;
	//	cout<<"s";
		
	}
//	cout<<"p";
//	cout<<"b";
	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<<a[i]<<" ";
	}
	
	





}

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:33:8: warning: unused variable 'f' [-Wunused-variable]
   33 |   bool f=false;
      |        ^
xorsort.cpp:34:7: warning: unused variable 'z' [-Wunused-variable]
   34 |   int z=(power[i]&a[j]);
      |       ^
xorsort.cpp:23:5: warning: unused variable 'a1' [-Wunused-variable]
   23 | int a1[n+1];
      |     ^~

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