# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1025351 | tolbi | Xor Sort (eJOI20_xorsort) | C++17 | 41 ms | 1196 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,s;cin>>n>>s;
vector<int> arr(n);
for (int i = 0; i < n; ++i)
{
cin>>arr[i];
}
vector<pair<int,int>> ansarr;
if (s==2){
for (int bit = 22; bit >= 0; bit--){
for (int i = 0; i+1 < n; i++){
if (arr[i]&(1LL<<bit)){
if (arr[i+1]&(1LL<<bit)){
ansarr.push_back({i+1,i+2});
arr[i]^=arr[i+1];
}
else {
ansarr.push_back({i+2,i+1});
ansarr.push_back({i+1,i+2});
arr[i+1]^=arr[i];
arr[i]^=arr[i+1];
}
}
}
if ((n>=1) && (arr[n-1]&(1LL<<bit))){
n--;
}
}
}
else {
for (int i = n; i >= 1; i--){
int maele = 0;
for (int j = 0; j < i; j++){
if (arr[j]>arr[maele]) maele=j;
if (j+1<i){
ansarr.push_back({j+1,j+2});
}
}
for (int j = 0; j+1 < maele; j++){
ansarr.push_back({j+1,j+2});
}
for (int j = maele; j+1 < i; j++){
ansarr.push_back({j+2,j+1});
}
for (int k = maele; k + 1 < i; k++){
swap(arr[k],arr[k+1]);
}
}
for (int i = n; i >= 2; i--){
ansarr.push_back({i-1,i});
}
}
cout<<ansarr.size()<<endl;
for (int i = 0; i < ansarr.size(); ++i)
{
cout<<ansarr[i].first<<" "<<ansarr[i].second<<endl;
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |