oj.uz

Submission #1014358

# Submission time Handle Problem Language Result Execution time Memory
1014358 2024-07-04T18:35:47 Z EntityPlantt Xor Sort (eJOI20_xorsort) C++17
40 / 100
 4 ms 1040 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Not sorted
3 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Not sorted
3 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 992 KB Output is correct
7 Correct 3 ms 992 KB Output is correct
8 Correct 3 ms 992 KB Output is correct
9 Correct 3 ms 992 KB Output is correct
10 Correct 4 ms 992 KB Output is correct
11 Correct 3 ms 992 KB Output is correct
12 Correct 3 ms 992 KB Output is correct
13 Correct 4 ms 992 KB Output is correct
14 Correct 3 ms 1040 KB Output is correct
15 Correct 4 ms 992 KB Output is correct