oj.uz

Submission #843668

# Submission time Handle Problem Language Result Execution time Memory
843668 2023-09-04T11:38:08 Z Andrijanikolic73 Xor Sort (eJOI20_xorsort) C++17
0 / 100
 32 ms 980 KB 
#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+100);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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Incorrect 18 ms 724 KB Not sorted
5 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Incorrect 18 ms 724 KB Not sorted
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Incorrect 32 ms 980 KB Not sorted
5 Halted 0 ms 0 KB -