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
// Michał Seweryn
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
 
using namespace __gnu_pbds; // pb_ds in old gcc
 
using Int = long long;

using OrderedSet = tree<
    Int,                    // key type
    null_type,              // value type (for maps), null_mapped_type in old gcc
    std::less<Int>,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

int main(){
  std::ios_base::sync_with_stdio(false);
  Int n, k;
  std::cin >> n >> k;
  --k;
  Int num_pairs = n * (n - 1) / 2;
  if (num_pairs % 2 != 0) {
    std::cout << "NIE\n";
    return 0;
  }
  std::vector<std::vector<Int>> count(n + 1);
  auto Count = [&count](Int a, Int b) -> Int {
    b = std::min(b, a * (a - 1) / 2 - b);
    if (b < 0) return 0;
    return count[a][std::min(b,(Int) count[a].size() - 1)];
  };
  count[0].emplace_back(1);
  for (Int a = 1; a <= n; ++a) {
    for (Int b = 0; b <= a * (a - 1) / 2; ++b) {
      count[a].emplace_back(0);
      for (Int c = std::max(0ll, b - a * (a - 1) / 2);
          c <= std::min(b, a - 1); ++c) { // first_elem
        count[a][b] += Count(a - 1, b - c);
        count[a][b] = std::min(count[a][b], k + 1);
        if (count[a][b] == k + 1) {
          break;
        }
      }
      if (count[a][b] == k + 1) {
        break;
      }
    }
  }
  if (k >= Count(n, num_pairs / 2)) {
    std::cout << "NIE\n";
    return 0;
  }
  std::cout << "TAK\n";
  OrderedSet s;
  for (Int i = 1; i <= n; ++i) {
    s.insert(i);
  }
  Int m = num_pairs / 2;
  for (Int i = 0; i < n; ++i) {
    for (Int c = std::max(0ll, m - (n - i - 1) * (n - i - 2) / 2);
        c <= std::min(m, n - i - 1); ++c) {
      Int cnt = Count(n - i - 1, m - c);
      if (k < cnt) {
        auto it = s.find_by_order(c);
        std::cout << *it << ' ';
        s.erase(it);
        m -= c;
        break;
      }
      k -= cnt;
    }
  }
  std::cout << '\n';
}