Submission #457938

#TimeUsernameProblemLanguageResultExecution timeMemory
457938RaresFelixXor Sort (eJOI20_xorsort)C++17
0 / 100
1 ms300 KiB
#include <bits/stdc++.h> #define MN 10071 #define ML 20 using namespace std; int n, s, A[MN]; vector<pair<int, int> > SOL; void xo(int a, int b) { A[a] ^= A[b]; SOL.push_back({a, b}); } int main() { cin >> n >> s; for(int i = 1; i <= n; ++i) cin >> A[i]; if(s == 1 || n <= ML){ for(int i = 1; i <= n; ++i) for(int j = n; j >= 2; --j) if(A[j] < A[j-1]){ xo(j, j-1); xo(j-1, j); xo(j, j-1); } } else { for(int j = (ML-1); j >= 0; --j){ for(int i = 1; i < n + j - (ML-1); ++i){ if((A[i] & (1<<j)) && A[i+1] & (1<<j)) xo(i, i + 1); else if((A[i] & (1<<j))){ xo(i+1, i); xo(i, i + 1); } } } } for(int i = 1; i <= n; ++i) cout << A[i] << " \n"[i==n]; cout << SOL.size() << "\n"; for(auto it : SOL) cout << it.first << " " << it.second << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...