Submission #457940

# Submission time Handle Problem Language Result Execution time Memory
457940 2021-08-07T15:15:47 Z RaresFelix Xor Sort (eJOI20_xorsort) C++17
65 / 100
14 ms 1320 KB
#include <bits/stdc++.h>
#define MN 10071
#define ML 20
using namespace std;
int n, s, A[MN];
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)
            for(int j = n; j >= 2; --j)
                if(A[j] < A[j-1]){
                    xo(j, j-1);
                    xo(j-1, 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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 6 ms 680 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 840 KB Output is correct
13 Correct 9 ms 916 KB Output is correct
14 Correct 8 ms 932 KB Output is correct
15 Correct 11 ms 840 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 4 ms 588 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 6 ms 680 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 840 KB Output is correct
13 Correct 9 ms 916 KB Output is correct
14 Correct 8 ms 932 KB Output is correct
15 Correct 11 ms 840 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 5 ms 588 KB Output is correct
18 Correct 7 ms 844 KB Output is correct
19 Correct 7 ms 840 KB Output is correct
20 Correct 8 ms 840 KB Output is correct
21 Correct 7 ms 840 KB Output is correct
22 Correct 8 ms 792 KB Output is correct
23 Correct 8 ms 816 KB Output is correct
24 Correct 7 ms 788 KB Output is correct
25 Correct 7 ms 840 KB Output is correct
26 Incorrect 14 ms 1320 KB Integer 59568 violates the range [0, 40000]
27 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 8 ms 840 KB Output is correct
6 Correct 8 ms 892 KB Output is correct
7 Correct 7 ms 840 KB Output is correct
8 Correct 8 ms 848 KB Output is correct
9 Correct 8 ms 840 KB Output is correct
10 Correct 7 ms 840 KB Output is correct
11 Correct 8 ms 840 KB Output is correct
12 Correct 8 ms 840 KB Output is correct
13 Correct 8 ms 908 KB Output is correct
14 Correct 8 ms 840 KB Output is correct
15 Correct 10 ms 964 KB Output is correct