Submission #465935

#TimeUsernameProblemLanguageResultExecution timeMemory
465935Alen777Xor Sort (eJOI20_xorsort)C++14
40 / 100
77 ms1040 KiB
#include <iostream> #include <string> #include <iomanip> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <algorithm> #include <cstring> using namespace std; #define ll long long #define ull unsigned ll #define pb push_back #define mpr make_pair #define lb lower_bound #define ld long double #define ub upper_bound map<pair<int, int>, bool> m; int n, s; int a[100005]; void solve() { cin >> n >> s; for (int i = 0; i < n; i++) { cin >> a[i]; } vector<pair<int, int> > ans; if (s == 1) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { ans.push_back(mpr(j + 1, j + 2)); ans.push_back(mpr(j + 2, j + 1)); ans.push_back(mpr(j + 1, j + 2)); swap(a[j], a[j + 1]); } } } } else { for (int i = 1; i <= (1 << 20); i *= 2) { for (int j = 0; j < n - 1; j++) { if ((i & a[j]) && !(i & a[j + 1])) { ans.push_back(mpr(j + 1, j)); ans.push_back(mpr(j, j + 1)); a[j + 1] = a[j + 1] ^ a[j]; a[j] = a[j] ^ a[j + 1]; } else if (i & a[j]) { ans.push_back(mpr(j, j + 1)); a[j] = a[j] ^ a[j + 1]; } } } } cout << ans.size() << endl; for (auto i : ans) { cout << i.first + 1 << ' ' << i.second + 1 << endl; } } int main() { /*cout.setf(ios::fixed | ios::showpoint); cout.precision(6);*/ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...