oj.uz

Submission #1089432

# Submission time Handle Problem Language Result Execution time Memory
1089432 2024-09-16T13:30:30 Z ZyadH1 Xor Sort (eJOI20_xorsort) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
const int mxn = 501;

int n, s;
int A[300];
vector<pair<int, int>> ans; // Simplified to pair instead of array

inline void swp(int a, int b) {
    if (a > b) {
        for (int i = a; i > b; --i) {
            ans.push_back({i, i - 1});
            ans.push_back({i - 1, i});
            ans.push_back({i, i - 1});
            swap(A[i], A[i - 1]);
        }
    } else {
        for (int i = a; i < b; ++i) {
            ans.push_back({i, i + 1});
            ans.push_back({i + 1, i});
            ans.push_back({i, i + 1});
            swap(A[i], A[i + 1]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s;
    vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        b[i] = A[i];
    }

    sort(b.begin(), b.end());
    unordered_map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        mp[b[i]] = i;
    }

    for (int i = n - 1; i >= 0; --i) {
        if (i != mp[A[i]]) {
            swp(i, mp[A[i]]);
            ++i; // Continue from the next index after a swap
        }
    }

    for (const auto& p : ans) {
        cout << p.first + 1 << " " << p.second + 1 << endl;
    }
    cout << ans.size() << endl;

    return 0;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Not adjacent
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Not adjacent
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Not adjacent
2 Halted 0 ms 0 KB -