Submission #843667

#	Time	Username	Problem	Language	Result	Execution time	Memory
843667		Andrijanikolic73	Xor Sort (eJOI20_xorsort)	C++17	25 / 100	650 ms	12024 KiB

xorsort

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1001;
int n;
int s;
vector<pair<int,int>>v;
int a[N];
vector<pair<int,int>>V;
void zameni(int i,int j){
    v.push_back({i,j});
    v.push_back({j,i});
    v.push_back({i,j});
    for(auto it:v)a[it.first]^=a[it.second];
    for(auto it:v)V.push_back({it.first,it.second});
    v.clear();
}
void Swap(int i,int j){
    while(j>i){
        zameni(j-1,j);
        j--;
    }
}
signed main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++)cin>>a[i];
    // kako da zamenim dva suseda ???
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=min(n,i+256);j++){
            if(a[i]>a[j]){
                Swap(i,j);
            }
        }
    }
    cout<<V.size();
    cout<<endl;
    for(auto it:V){
        cout<<it.first<<" "<<it.second;
        cout<<endl;
    }
}
/*
5 1
3 2 8 4 1
*/
/*
max 40000 operacija
s=1 a[i]<a[i+1]
s=2 a[i]<=a[i+1]
*/

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