Submission #815766

#	Time	Username	Problem	Language	Result	Execution time	Memory
815766		ThylOne	Xor Sort (eJOI20_xorsort)	C++14	65 / 100	77 ms	1244 KiB

xorsort

#include<bits/stdc++.h>

using namespace std;
vector<pair<int,int>> ans;
void swapA(int i,int j){
	ans.push_back(make_pair(j,i));
	ans.push_back(make_pair(i,j));
	ans.push_back(make_pair(j,i));

}


void binaryPrint(int n, int log=6){
	for(int i=log-1;i>=0;i--){
		if(n&1){
			cout<<"1";
		}else{
			cout<<"0";
		}
		n>>=1;
	}
	cout<<endl;
}
#define debug for(int i = 0 ; i < n ; i++)binaryPrint(nums[i]);cout<<endl;
int main(){
	int n,s;cin>>n>>s;
	vector<int> nums(n);
	for(int i = 0 ; i <n;i++){
		cin>>nums[i];
	}
	if(s==1){
		
		for(int pos=0;pos<n;pos++){
			for(int i=0;i<n-1;i++){
				if(nums[i]>nums[i+1]){
					swap(nums[i],nums[i+1]);
					swapA(i,i+1);
				}
			}
		}
		
		}else{
			//s==2
			int last=n;
			
			for(int BIT=19;BIT>=0;BIT--){
				int ID=-1;
				for(int i=0;i<last;i++){
					if((nums[i]>>BIT)&1){
						ID=i;
						break;
					}
				}
				if(ID==-1)continue;
				for(int i=ID;i<last-1;i++){
					if(!((nums[i+1]>>BIT)&1)){
						ans.push_back(make_pair(i+1,i));
						nums[i+1]=nums[i+1]^nums[i];
					}
				}
				for(int i=ID;i>0;i--){
					if(!((nums[i-1]>>BIT)&1)){
						ans.push_back(make_pair(i-1,i));
						nums[i-1]=nums[i-1]^nums[i];
					}
				}
				
				//On détruit tout les bits sauf 1
				for(int i=1;i<last;i++){
					// ans i i+1
					ans.push_back(make_pair(i-1,i));
					nums[i-1]=nums[i-1]^nums[i];
				}
				last--;
				
			}
			
		}
		cout<<ans.size()<<endl;
		for(auto&p:ans){
			cout<<p.first+1<<' '<<p.second+1<<endl;
		}
		
	
	return 0;
}

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