oj.uz

Submission #529294

# Submission time Handle Problem Language Result Execution time Memory
529294 2022-02-22T16:49:52 Z Itamar Xor Sort (eJOI20_xorsort) C++14
0 / 100
 68 ms 6312 KB 
#include <map>
using namespace std;
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <iostream>

vector<pair<int, int>> ans;
vector<int> v;
int k;

int main()
{
    int n, s;
    cin >> n >> s;
    v.resize(n);
    int siz = n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v[i] = x;
    }
    

     k = 0;
    int t = 1;
    while (t < 1e6) {
        t *= 2;
    }
    t = t / 2;
    bool f = 1;
    while (f) {
        for (int i = 0; i < siz; i++) {
            if (v[i] >= t) {
                f = 0;
                for (int j = i; j < siz - 1; j++) {
                    if (v[j+1] < t) {
                        v[j + 1] = v[j] ^ v[j + 1];
                        k++;
                        ans.push_back({ j + 1,j });
                    }
                }
                if (i >= siz / 2) {
                    for (int j = i - 1; j >= siz / 2; j--) {
                        v[j] = v[j] ^ v[j + 1];
                        k++;
                        ans.push_back({ j ,j + 1 });
                    }
                }
                else {
                    for (int j = i; j < siz / 2; j++) {
                        v[j] = v[j] ^ v[j + 1];
                        k++;
                        ans.push_back({ j ,j + 1 });
                    }
                }
                break;
            }
        }
        t /= 2;
    }
    f = 1;
    while (f) {
        f = 0;
        for (int i = 0; i < siz / 2 -1; i++) {
            if (v[i] >= v[i + 1]) {
                int c = v[i];
                v[i] = v[i + 1];
                v[i + 1] = c;
                ans.push_back({ i , i+1 });
                ans.push_back({ i+1 , i  });
                ans.push_back({ i , i + 1 });
                k += 3;
                f = 1;
            }
        }
    }
    f = 1;
    while (f) {
        f = 0;
        for (int i = siz/2; i < siz - 1; i++) {
            if (v[i] > v[i + 1]) {
                int c = v[i];
                v[i] = v[i + 1];
                v[i + 1] = c;
                ans.push_back({ i , i + 1 });
                ans.push_back({ i + 1 , i });
                ans.push_back({ i , i + 1 });
                k += 3;
                f = 1;
            }
        }
    }
    cout << k << "\n";
    for (int i = 0; i < k; i++) {
        cout << ans[i].first+1 << ' ' << ans[i].second+1 << "\n";
    }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Incorrect 2 ms 460 KB Not sorted
6 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Incorrect 2 ms 460 KB Not sorted
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Incorrect 68 ms 6312 KB Integer 379115 violates the range [0, 40000]
6 Halted 0 ms 0 KB -