Submission #707946

#	Time	Username	Problem	Language	Result	Execution time	Memory
707946		josanneo22	Xor Sort (eJOI20_xorsort)	C++17	60 / 100	193 ms	1924 KiB

xorsort

#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define ld long double
#define pll pair <ll,ll>
#define F first
#define S second
#define pb push_back
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;

int n, type;
vector <ll> a;
vector <pll> ans;
void solve1() {
	int mn = 2e9;
	vector <pll> ans2;
	for (int i = 0; i < n - 1; i++)
		a[i] ^= a[i + 1];
	for (int j = 0; j < n; j++) {
		vector<ll> aa;
		aa = a;
		for (int i = 0; i < n; i++)
			if (i != j) a[i] ^= a[j];
		ans.clear();
		vector<ll> ab;
		ab = aa;
		for (int i = 0; i < n - 1; i++)
			ans.pb({ i + 1,i + 2 });
		for (int i = j + 1; i < n; i++)
		{
			ans.pb({ i + 1,i });
			ab[i] ^= ab[i - 1];
		}
		for (int i = j - 1; i >= 0; i--)
		{
			ans.pb({ i + 1,i + 2 });
			ab[i] ^= ab[i + 1];
		}
		a = ab;
		unordered_map<int, int> mp;
		bool YY = true;
		for (int i = 0; i < n; i++)
		{
			if (mp[a[i]]) { YY = false; break; }
			++mp[a[i]];
		}
		if (YY == false) {
			a = aa;
			continue;
		}
		while (1) {
			bool found = true;
			int mx = -1;
			int pos = -1;
			for (int i = 0; i < n - 1; i++)
				if (a[i] > a[i + 1]) {
					pos = i;
					break;
				}
			if (pos < 0) break;
			ans.pb({ pos + 2,pos + 1 });
			ans.pb({ pos + 1, pos + 2 });
			ans.pb({ pos + 2,pos + 1 });
			swap(a[pos], a[pos + 1]);
		}
		if (ans.size() < mn) {
			mn = ans.size();
			ans2 = ans;
		}
		a = aa;

	}
	ans = ans2;
	cout << ans.size() << '\n';
	for (auto to : ans)
		cout << to.F << " " << to.S << '\n';
}
void solve2() {
	int m = n;
	for (int i = 19; i >= 0; i--)
	{
		int st = 0;
		for (int j = 0; j < m - 1; j++)
		{
			if (a[j] & (1 << i) && a[j + 1] & (1 << i))
			{
				st = 1;
				ans.push_back({ j, j + 1 });
				a[j] ^= a[j + 1];
			}
			else if (a[j] & (1 << i))
			{
				st = 1;
				ans.push_back({ j + 1, j });
				ans.push_back({ j, j + 1 });
				a[j + 1] ^= a[j];
				a[j] ^= a[j + 1];
			}
		}
		if (st)
			m--;
	}
	cout << ans.size() << '\n';
	for (auto to : ans)
		cout << to.F << " " << to.S << '\n';
}

int main() {
	cin >> n >> type;
	a.resize(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	if (type == 1) solve1();
	else solve2();
}

Compilation message (stderr)

xorsort.cpp: In function 'void solve1()':
xorsort.cpp:53:9: warning: unused variable 'found' [-Wunused-variable]
   53 |    bool found = true;
      |         ^~~~~
xorsort.cpp:54:8: warning: unused variable 'mx' [-Wunused-variable]
   54 |    int mx = -1;
      |        ^~
xorsort.cpp:67:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |   if (ans.size() < mn) {
      |       ~~~~~~~~~~~^~~~

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