oj.uz

Submission #720157

# Submission time Handle Problem Language Result Execution time Memory
720157 2023-04-07T13:59:41 Z fuad27 Xor Sort (eJOI20_xorsort) C++17
100 / 100
 10 ms 972 KB 
#include<bits/stdc++.h>
using namespace std;
int main () {
  int n, s;
  cin >> n >> s;
  int a[n];
  for(int i = 0;i<n;i++)cin >> a[i];
  vector<pair<int,int>> op;
  if(s==2) {
    for(int i = 19;i>=0;i--) {
      for(int j = 1;j<n;j++) {
        if((a[j]&(1<<i))==0 and (a[j-1]&(1<<i))!=0) {
          a[j]^=a[j-1];
          op.push_back({j,j-1});
        }
        if((a[j-1]&(1<<i))!=0) {
          if((a[j-1]^a[j])<a[j-1]) {
            a[j-1]^=a[j];
            op.push_back({j-1,j});
          }
        }
      }
    }
    cout << op.size() << "\n";
    for(auto i:op) {
      cout << i.first+1 << " " << i.second+1 << "\n";
    }
  }
  else {
    int x=0;
    for(int i = 0;i<n-1;i++) {
      int mx=0;
      for(int j = 0;j<n-i;j++) {
        if((a[j]^x)>(a[mx]^x))mx=j;
      }
      for(int j = 0;j<n-i;j++) {
        if(j!=n-1) {
          op.push_back({j,j+1});
          a[j]^=a[j+1];
        }
      }
      for(int j = mx;j<n-i-1;j++) {
        a[j+1]^=a[j];
        op.push_back({j+1,j});
      }
      for(int j = mx-2;j>=0;j--) {
        a[j]^=a[j+1];
        op.push_back({j,j+1});
      }
      x=a[n-i-1];
    }
    a[0]^=a[1];
    op.push_back({0,1});
    cout << op.size() << "\n";
    for(auto i:op) {
      cout << i.first+1 << " " << i.second+1 << "\n";
    }
  }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 720 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 4 ms 720 KB Output is correct
7 Correct 5 ms 720 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 4 ms 684 KB Output is correct
10 Correct 4 ms 688 KB Output is correct
11 Correct 4 ms 684 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 6 ms 680 KB Output is correct
14 Correct 4 ms 720 KB Output is correct
15 Correct 5 ms 720 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 720 KB Output is correct
5 Correct 4 ms 720 KB Output is correct
6 Correct 4 ms 720 KB Output is correct
7 Correct 5 ms 720 KB Output is correct
8 Correct 5 ms 720 KB Output is correct
9 Correct 4 ms 684 KB Output is correct
10 Correct 4 ms 688 KB Output is correct
11 Correct 4 ms 684 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 6 ms 680 KB Output is correct
14 Correct 4 ms 720 KB Output is correct
15 Correct 5 ms 720 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 5 ms 684 KB Output is correct
18 Correct 8 ms 972 KB Output is correct
19 Correct 8 ms 932 KB Output is correct
20 Correct 8 ms 972 KB Output is correct
21 Correct 8 ms 932 KB Output is correct
22 Correct 7 ms 972 KB Output is correct
23 Correct 7 ms 932 KB Output is correct
24 Correct 7 ms 972 KB Output is correct
25 Correct 7 ms 932 KB Output is correct
26 Correct 8 ms 936 KB Output is correct
27 Correct 8 ms 972 KB Output is correct
28 Correct 10 ms 972 KB Output is correct
29 Correct 8 ms 972 KB Output is correct
30 Correct 8 ms 972 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 6 ms 892 KB Output is correct
6 Correct 6 ms 848 KB Output is correct
7 Correct 9 ms 848 KB Output is correct
8 Correct 6 ms 892 KB Output is correct
9 Correct 6 ms 864 KB Output is correct
10 Correct 6 ms 848 KB Output is correct
11 Correct 6 ms 848 KB Output is correct
12 Correct 6 ms 936 KB Output is correct
13 Correct 6 ms 848 KB Output is correct
14 Correct 6 ms 936 KB Output is correct
15 Correct 7 ms 972 KB Output is correct