Submission #457986

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
457986	2021-08-07 17:20:59	RaresFelix	Xor Sort (eJOI20_xorsort)	C++17	40 / 100	12 ms	4680 KiB

xorsort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define MN 10071
#define ML 20
using namespace std;
int n, s, A[MN];
int F[(1<<21)];
vector<pair<int, int> > SOL;
void xo(int a, int b) {
    --F[A[a]];
    A[a] ^= A[b];
    ++F[A[a]];
    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]){
                    if(F[A[j] ^ A[j-1]] || (A[j] ^ A[j-1]) > A[j]){
                        xo(j, j-1);
                        xo(j-1, j);
                        xo(j, j-1);
                    }
                    else {
                        xo(j-1, j);
                    }
                }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 40 / 40