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
#include <stdio.h>

#include <algorithm>
#include <optional>
#include <set>
#include <vector>

std::optional<std::vector<int>> check(const std::vector<int>& data, const std::vector<int>& min, const std::vector<int>& max, const int n, const int k, const int a, const int b) {
  if (4 <= k) {
    return {{a, b, b + 1}};
  } else {
    const auto aOk = a == 0 || data[b] <= min[a - 1];
    const auto bOk = b == n - 1 || max[b + 1] <= data[a];
    if (3 <= k && aOk) {
      return {{b, b + 1}};
    } else if (3 <= k && bOk) {
      return {{a, b}};
    } else if (2 <= k && max[b] <= min[a]) {
      return {{b}};
    }
  }
  return std::nullopt;
}

std::optional<std::vector<int>> resolve(const std::vector<int>& data, const std::vector<int>& min, const std::vector<int>& max, const int n, const int k) {
  for (int i = 0; i < data.size() - 1; ++i) {
    if (data[i + 1] <= data[i]) {
      const auto solution = check(data, min, max, n, k, i, i + 1);
      if (solution) {
        return solution;
      }
    }
  }
  return std::nullopt;
}

void calculateMinMax(const std::vector<int>& data, std::vector<int>& min, std::vector<int>& max) {
  int _min = 1000000001;
  int _max = -1000000001;
  for (const auto& value : data) {
    _min = std::min(_min, value);
    min.push_back(_min);
  }
  for (auto it = data.rbegin(); it != data.rend(); ++it) {
    _max = std::max(_max, *it);
    max.push_back(_max);
  }
  std::reverse(max.begin(), max.end());
}

int main() {
  int n, k, tmp;
  std::vector<int> data, min, max;
  scanf("%d %d\n", &n, &k);
  data.reserve(n);
  min.reserve(n);
  max.reserve(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &tmp);
    data.push_back(tmp);
  }
  calculateMinMax(data, min, max);
  const auto solution = resolve(data, min, max, n, k);
  if (solution) {
    int toPrint = k - solution->size() - 1;
    printf("TAK\n");
    for (int i = 1; i < solution->front(); ++i) {
      if (0 < toPrint--)
        printf("%d ", i);
    }
    for (const auto& value : solution.value()) {
      printf("%d ", value);
    }
    for (int i = solution->back() + 1; i < n; ++i) {
      if (0 < toPrint--)
        printf("%d ", i);
    }
    printf("\n");
  } else {
    printf("NIE\n");
  }
  return 0;
}