Submission #774815

#TimeUsernameProblemLanguageResultExecution timeMemory
774815vjudge1Xor Sort (eJOI20_xorsort)C++17
0 / 100
1 ms320 KiB
#include <bits/stdc++.h> using namespace std; int n, s; vector<pair<int, int>> v; vector<int> valueToIndex, indexToValue; vector<pair<int, int>> operations; void performSwap(const int& i, const int& j) { assert(max(i - j, j - i) == 1); operations.emplace_back(i, j); operations.emplace_back(j, i); operations.emplace_back(i, j); } int main() { // freopen("inp.txt", "r", stdin); ios::sync_with_stdio(false); cin >> n >> s; v.resize(n); for (int i = 0; i < n; i++) { cin >> v[i].first; v[i].second = i; } sort(v.begin(), v.end()); valueToIndex.resize(n); indexToValue.resize(n); for (int i = 0; i < n; i++) { indexToValue[v[i].second] = i; valueToIndex[indexToValue[i]] = i; } for (int i = 0; i < n; i++) { int x = valueToIndex[i]; for (int i1 = x; i1 > i; i1--) { int index = valueToIndex[i]; int otherIndex = index - 1; int prevValueAtIndex = i; int prevValueAtOtherIndex = indexToValue[otherIndex]; valueToIndex[prevValueAtIndex] = otherIndex; indexToValue[otherIndex] = prevValueAtIndex; valueToIndex[prevValueAtOtherIndex] = index; indexToValue[index] = prevValueAtOtherIndex; performSwap(index, otherIndex); } } cout << operations.size() << '\n'; for (auto &operation : operations) cout << operation.first + 1 << ' ' << operation.second + 1 << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...