Submission #1014358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014358		EntityPlantt	Xor Sort (eJOI20_xorsort)	C++17	40 / 100	4 ms	1040 KiB

xorsort

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1005;
int arr[N], elms[N];
vector <pair <int, int>> oper;

void makexor(int a, int b, bool change = true) {
	if (change) arr[a] = arr[a] ^ arr[b];
	/* if (!oper.empty() && oper.back() == pair{a, b}) oper.pop_back();
	else */ oper.emplace_back(a, b);
}
void fixzeroes(int nowat) {
	for (int i = 1; i < nowat; i++) {
		if (arr[i - 1] && !arr[i]) makexor(i, i - 1);
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	char s;
	cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> arr[i];
	if (s == '2') {
		int nowat = n;
		while (true) {
			int largestBit = 0;
			for (int i = 0; i < nowat; i++) {
				if ((1 << largestBit) <= arr[i]) {
					while ((1 << largestBit) <= arr[i]) largestBit++;
					largestBit--;
				}
			}
			if (!largestBit) break;
			nowat--;
			for (int i = 0; i < nowat; i++) {
				if ((1 << largestBit) & arr[i]) {
					if (!((1 << largestBit) & arr[i + 1])) makexor(i + 1, i);
					makexor(i, i + 1);
				}
			}
		}
		fixzeroes(nowat);
	}
	else {
		copy(arr, arr + n, elms);
		for (int i = 1; i < n; i++) makexor(i - 1, i);
		for (int i = n - 1; i; i--) {
			int x = distance(elms, max_element(elms, elms + i + 1));
			if (x == i) continue;
			for (int j = x; j < i; j++) makexor(j + 1, j);
			for (int j = max(x - 1, 0); j < i; j++) makexor(j, j + 1);
			for (int j = x; j < i; j++) swap(elms[j], elms[j + 1]);
		}
		// for (int i = 0; i < n; i++) cerr << arr[i] << ' ';
	}
	cout << oper.size();
	for (auto &p : oper) cout << '\n' << p.first + 1 << ' ' << p.second + 1;
	return 0;
}

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