oj.uz

Submission #425576

# Submission time Handle Problem Language Result Execution time Memory
425576 2021-06-13T07:50:18 Z MilosMilutinovic Xor Sort (eJOI20_xorsort) C++14
0 / 100
 1 ms 332 KB 
#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;
  cin >> n;

  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

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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Not sorted
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Not sorted
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Not sorted
2 Halted 0 ms 0 KB -