oj.uz

Submission #425577

# Submission time Handle Problem Language Result Execution time Memory
425577 2021-06-13T07:50:40 Z MilosMilutinovic Xor Sort (eJOI20_xorsort) C++14
25 / 100
 150 ms 12536 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, 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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 4 ms 696 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 4 ms 672 KB Output is correct
10 Correct 6 ms 592 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 7 ms 848 KB Output is correct
13 Correct 8 ms 976 KB Output is correct
14 Correct 7 ms 976 KB Output is correct
15 Correct 7 ms 976 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 4 ms 696 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 4 ms 592 KB Output is correct
9 Correct 4 ms 672 KB Output is correct
10 Correct 6 ms 592 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 7 ms 848 KB Output is correct
13 Correct 8 ms 976 KB Output is correct
14 Correct 7 ms 976 KB Output is correct
15 Correct 7 ms 976 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 4 ms 592 KB Output is correct
18 Correct 7 ms 848 KB Output is correct
19 Correct 7 ms 848 KB Output is correct
20 Correct 7 ms 848 KB Output is correct
21 Correct 6 ms 848 KB Output is correct
22 Correct 6 ms 848 KB Output is correct
23 Correct 6 ms 848 KB Output is correct
24 Correct 6 ms 828 KB Output is correct
25 Correct 6 ms 848 KB Output is correct
26 Incorrect 15 ms 1276 KB Integer 59568 violates the range [0, 40000]
27 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6 ms 848 KB Output is correct
5 Incorrect 150 ms 12536 KB Integer 764742 violates the range [0, 40000]
6 Halted 0 ms 0 KB -