beecrowd/1252.c at main · guhkadoo/beecrowd · GitHub

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>

typedef struct Node {
    int num;
    int remainder;
    int is_even;
} vector;

void swap(int *n1, int *n2) {
    if (n1 != n2) {
        *n1 = *n1 ^ *n2;
        *n2 = *n1 ^ *n2;
        *n1 = *n1 ^ *n2;
    }
}

void swap_vector(vector *v1, vector *v2) {
    swap(&v1->remainder, &v2->remainder);
    swap(&v1->is_even, &v2->is_even);
    swap(&v1->num, &v2->num);
}

int lomuto(vector *v[], int low, int high) {
    vector *pivot = v[high];
    int boundary = low;
    for (int i = low; i < high; i++) {
        if (v[i]->remainder < pivot->remainder) {
            if(v[boundary] == pivot)
                pivot = v[i];
            swap_vector(v[i], v[boundary++]);
        } else if(v[i]->remainder == pivot->remainder) {
            if(!pivot->is_even) {
                if(!v[i]->is_even && v[i]->num > pivot->num)
                    pivot = v[i];
            } else {
                if(!v[i]->is_even)
                    pivot = v[i];
                else {
                    if(v[i]->num < pivot->num)
                        pivot = v[i];
                }
            }
        }
    }
    swap_vector(pivot, v[boundary]);
    return boundary;
}

void quick_sort(vector *v[], int low, int high) {
    if (low < high) {
        int boundary = lomuto(v, low, high);

        quick_sort(v, low, boundary - 1);
        quick_sort(v, boundary + 1, high);
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d %d\n", n, m);

    while (n || m) {
        vector v[n];               // Array of structs
        vector *vp[n];             // Array of pointers to structs

        for (int i = 0; i < n; i++) {
            scanf("%d", &v[i].num);

            v[i].is_even = !(v[i].num & 1); // Check if even
            v[i].remainder = v[i].num % m;

            vp[i] = &v[i]; // Assign pointer to the struct
        }

        quick_sort(vp, 0, n-1);

        for (int i = 0; i < n; i++) {
            printf("%d\n", vp[i]->num);
        }

        scanf("%d%d", &n, &m);
        printf("%d %d\n", n, m);
    }

    return 0;
}