Submission #425577

#	Time	Username	Problem	Language	Result	Execution time	Memory
425577		MilosMilutinovic	Xor Sort (eJOI20_xorsort)	C++14	25 / 100	150 ms	12536 KiB

xorsort

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long unsigned long ull;
typedef double long ld;

int main() {
  ios::sync_with_stdio(!cin.tie(0));

  int n, s;
  cin >> n >> s;

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  auto b = a;
  sort(b.begin(), b.end());

  vector<pair<int, int>> ans;

  for (int i = 0; i < n; i++) {
    int pos;
    for (int j = 0; j < n; j++) {
      if (a[j] == b[i]) {
        pos = j;
      }
    }
    while (pos > i) {
      ans.push_back({pos, pos - 1}); // a = a ^ b
      ans.push_back({pos - 1, pos}); // b = b ^ (a ^ b) = a
      ans.push_back({pos, pos - 1}); // a = a ^ b ^ a = b
      swap(a[pos], a[pos - 1]);
      pos--;
    }
  }

  cout << ans.size() << '\n';
  for (auto& p : ans) {
    cout << p.first + 1 << " " << p.second + 1 << '\n';
  }
}

/*a, b
a = a ^ b
b = b ^ (a ^ b) = a
a = a ^ b ^ a


3 op to swap*/

Compilation message (stderr)

xorsort.cpp: In function 'int main()':
xorsort.cpp:25:9: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |     int pos;
      |         ^~~

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