oj.uz

Submission #508487

# Submission time Handle Problem Language Result Execution time Memory
508487 2022-01-13T11:27:32 Z uncripted Xor Sort (eJOI20_xorsort) C++11
0 / 100
 1 ms 304 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 304 KB Not sorted
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 304 KB Not sorted
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Extra information in the output file
2 Halted 0 ms 0 KB -