Submission #720140

#	Time	Username	Problem	Language	Result	Execution time	Memory
720140		fuad27	Xor Sort (eJOI20_xorsort)	C++17	65 / 100	73 ms	1160 KiB

xorsort

#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v;
void sw(int i, int j) {
	v.push_back({j, i});
	v.push_back({i, j});
	v.push_back({j, i});
}
int main () {
  int n, s;
  cin >> n >> s;
  int a[n];
  for(int i = 0;i<n;i++)cin >> a[i];
  if(s==2) {
    vector<pair<int,int>> op;
    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 {
    for(int i = 1;i<=n;i++) {
      bool check = false;
      for(int j = 0;j<n-i;j++) {
        if(a[j] > a[j+1]) {
          sw(j+1, j+2);
          swap(a[j], a[j+1]);
          check = true;
        }
      }
      if(!check)break;
    }
    cout<<v.size()<<endl;
    for(auto [i, j]:v) {
      cout<<i<<' '<<j<<endl;
    }
  }
}

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