oj.uz

Submission #642147

# Submission time Handle Problem Language Result Execution time Memory
642147 2022-09-18T15:03:29 Z Kanimet0 Xor Sort (eJOI20_xorsort) C++17
100 / 100
 9 ms 1020 KB 
#include <bits/stdc++.h>
#define MN 10071
#define ML 20
using namespace std;
int n, s, A[MN], B[MN];
int F[(1<<21)];
vector<pair<int, int> > SOL;
void xo(int a, int b) {
    A[a] ^= A[b];
    SOL.push_back({a, b});
}
int main() {
    cin >> n >> s;
    for(int i = 1; i <= n; ++i)
        cin >> A[i];
    if(s == 1 || n <= ML){
        for(int i = 1; i <= n; ++i) B[i] = A[i];
        for(int i = 1; i < n; ++i) xo(i, i+1);
        int pma = 0;
        for(int i = 0; i < n-1; ++i){
            pma = 0;
            for(int j = 1; j <= n - i; ++j)
                if(B[j] > B[pma]) pma = j;
            for(int j = pma+1; j <= n - i; ++j){
                xo(j, j-1);
                swap(B[j], B[j-1]);
            }
            for(int j = max(pma-1, 1); j < n-i; ++j)
                xo(j, j+1);
        }
    } else {
        for(int j = (ML-1); j >= 0; --j){
            for(int i = 1; i < n + j - (ML-1); ++i){
                if((A[i] & (1<<j)) && A[i+1] & (1<<j)) xo(i, i + 1);
                else if((A[i] & (1<<j))){
                    xo(i+1, i);
                    xo(i, i + 1);
                }
            }
        }
    }
    cout << SOL.size() << "\n";
    for(auto it : SOL) cout << it.first << " " << it.second << "\n";
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 4 ms 584 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 5 ms 720 KB Output is correct
14 Correct 5 ms 692 KB Output is correct
15 Correct 5 ms 720 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 4 ms 584 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 4 ms 720 KB Output is correct
13 Correct 5 ms 720 KB Output is correct
14 Correct 5 ms 692 KB Output is correct
15 Correct 5 ms 720 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 3 ms 596 KB Output is correct
18 Correct 5 ms 720 KB Output is correct
19 Correct 5 ms 724 KB Output is correct
20 Correct 5 ms 720 KB Output is correct
21 Correct 4 ms 720 KB Output is correct
22 Correct 4 ms 724 KB Output is correct
23 Correct 4 ms 720 KB Output is correct
24 Correct 4 ms 724 KB Output is correct
25 Correct 6 ms 724 KB Output is correct
26 Correct 8 ms 940 KB Output is correct
27 Correct 8 ms 976 KB Output is correct
28 Correct 9 ms 976 KB Output is correct
29 Correct 8 ms 972 KB Output is correct
30 Correct 7 ms 932 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 6 ms 844 KB Output is correct
6 Correct 6 ms 820 KB Output is correct
7 Correct 6 ms 916 KB Output is correct
8 Correct 6 ms 904 KB Output is correct
9 Correct 6 ms 848 KB Output is correct
10 Correct 6 ms 848 KB Output is correct
11 Correct 7 ms 816 KB Output is correct
12 Correct 6 ms 952 KB Output is correct
13 Correct 7 ms 880 KB Output is correct
14 Correct 6 ms 848 KB Output is correct
15 Correct 9 ms 1020 KB Output is correct