oj.uz

Submission #465935

# Submission time Handle Problem Language Result Execution time Memory
465935 2021-08-17T11:27:16 Z Alen777 Xor Sort (eJOI20_xorsort) C++14
40 / 100
 77 ms 1040 KB 
#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;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Integer 6 violates the range [1, 5]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Integer 6 violates the range [1, 5]
2 Halted 0 ms 0 KB -

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 10 ms 460 KB Output is correct
5 Correct 50 ms 812 KB Output is correct
6 Correct 51 ms 856 KB Output is correct
7 Correct 50 ms 852 KB Output is correct
8 Correct 51 ms 868 KB Output is correct
9 Correct 50 ms 824 KB Output is correct
10 Correct 50 ms 844 KB Output is correct
11 Correct 50 ms 836 KB Output is correct
12 Correct 51 ms 956 KB Output is correct
13 Correct 55 ms 844 KB Output is correct
14 Correct 52 ms 848 KB Output is correct
15 Correct 77 ms 1040 KB Output is correct