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
#include <cstdio>
#include <algorithm>

const int max_n = 600000;
const int max_val = 1000000009;

int n, k;
int input[max_n];
int prev_min[max_n];
int suf_max[max_n];
int longest_streak[max_n];

int main() {
  scanf("%d %d", &n, &k);
  prev_min[0] = max_val;
  longest_streak[0] = 0;
  input[0] = max_val;
  for (int i = 1; i<= n; ++i) {
    scanf("%d", &input[i]);
    prev_min[i] = std::min(input[i], prev_min[i - 1]);
    if (input[i] > input[i - 1]) longest_streak[i] = 1 + longest_streak[i - 1];
    else longest_streak[i] = 1;
  }
  suf_max[n + 1] = -max_val;
  for (int i = n; i >= 1; --i) {
    suf_max[i] = std::max(suf_max[i + 1], input[i]);
  }
  for (int i = 1; i <= n - k + 1; ++i) {
    int first_group = prev_min[i];
    int last_group = suf_max[i + k - 1];
    // check the in the middle.
    if (k == 2) {
      if (first_group >= last_group) {
        printf("TAK\n");
        for (int j = 0; j < k - 1; ++j) {
          printf("%d ", i + j);
        }
        printf("\n");
        return 0;
      }
    } else {
      // k >= 3
      // is first_group < input[i + 1] < .. < input[i + k - 2] < last_group ?
      if (first_group >= input[i + 1] || input[i + k - 2] >= last_group ||
          longest_streak[i + k - 2] < k - 2) {
        printf("TAK\n");
        for (int j = 0; j < k - 1; ++j) {
          printf("%d ", i + j);
        }
        printf("\n");
        return 0;
      }
    }
  }
  printf("NIE\n");
  return 0;
}