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
#include <iostream>
#include <vector>

int main() {
    std::size_t n, k;
    std::cin >> n >> k;

    auto inversion_no = n * (n - 1);
    if (inversion_no % 4 != 0) {
        std::cout << "NIE\n";
        return 0;
    }
    inversion_no /= 4;

    std::vector<std::size_t> inversions(n, 0);

    for (std::size_t i = 0, j = 1; i < inversion_no; ++i) {
        ++inversions[j];
        if (inversions[j] >= j) {
            ++j;
        }
    }

    for (std::size_t i = 1; i < k; ++i) {
        for (std::size_t j = 1; j < n; ++j) {
            if (inversions[j] > 0 && inversions[j + 1] < j + 1) {
                --inversions[j];
                ++inversions[j + 1];

                for (std::size_t k = 1; k < j; ++k) {
                    if (inversions[k + 1] > 0 && inversions[k] < k) {
                        --inversions[k + 1];
                        ++inversions[k];
                    }
                }

                goto next;
            }
        }

        std::cout << "NIE\n";
        return 0;

next: ;
    }

    std::cout << "TAK\n";

    std::vector<bool> used(n, false);

    for (std::size_t i = n; i > 0; --i) {
        std::size_t skip = inversions[i - 1];

        for (std::size_t j = 0; ; ++j) {
            if (!used[j]) {
                if (skip == 0) {
                    used[j] = true;
                    std::cout << j + 1 << " ";
                    break;
                } else {
                    --skip;
                }
            }
        }
    }

    std::cout << "\n";
}