Submission #826711

#	Time	Username	Problem	Language	Result	Execution time	Memory
826711		ZeroCool	Xor Sort (eJOI20_xorsort)	C++14	100 / 100	45 ms	1484 KiB

xorsort

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
using namespace std;
 
const int mxn = 1005;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 998244353;
const ld eps = 1e-9;

int n;
int A[mxn];

vector<pair<int,int> >res;

void op(int a,int b){
	res.push_back({a+1,b+1});
	A[a] ^= A[b];
}

inline bool bit(int x,int i){
	return x & (1 << i);
}

void s1(){
	int B[n];
	for(int i = 0;i<n;i++)B[i] = A[i];

	for(int i = 0;i<n-1;i++)op(i,i + 1);

	for(int i = n-1;i>=0;i--){
		int k = 0;
		for(int j = 1;j<=i;j++){
			if(B[j] > B[k])k = j;
		}
		for(int j = k+1;j<=i;j++)op(j,j-1);
		for(int j = k-1;j<i;j++){
			if(j != -1)op(j,j+1);
		}

		for(int j = k;j<i;j++)swap(B[j], B[j+1]);
	}
}

void s2(){
	int last = n;
	for (int i = LOG-1; i >= 0; i--){
		bool ok = false;
		for (int j = 0; j < n; j++)
			if (bit(A[j], i)){
				ok = true;
				break;
			}
		if (!ok) continue;
		last--;
		for (int j = 0; j < last; j++)
			if (bit(A[j], i) && !bit(A[j+1], i)){
				op(j+1, j);
				op(j, j+1);
			}
			else if (bit(A[j], i) && bit(A[j+1], i)){
				op(j, j+1);
			}
	}
}

void solve(int T){
	cin>>n;
	int s;
	cin>>s;
	for(int i = 0;i<n;i++)cin>>A[i];

	if(s == 1)s1();
	else s2();

	cout<<res.size()<<endl;
	for(auto p : res)cout<<p.first<<" "<<p.second<<endl;

}
int32_t main(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	int t = 1;
	//cin>>t;

	for(int i = 1;i<=t;i++)solve(i);
    return 0;
}

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