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>
const int C=1000001;

int obligatory_places[C];
void print_result(int found, int k){
	for (int i=0; found < k-1; i++){
		if (!obligatory_places[i]) obligatory_places[i] = true, found++;
	}

        printf ("TAK\n");
	for (int i=0; found > 0; i++){
		if (obligatory_places[i]){
		       	printf ("%d ", i+1);
			found--;
		}
	}
	printf ("\n");
}

int seq[C], cur_min_lr[C], cur_max_rl[C];
int main(){
	int n, k;
	scanf ("%d %d", &n, &k);

	for (int i=0; i<n; i++) scanf ("%d", &seq[i]);

	int found = 0;
	if (k >= 4){
		for (int i=0; i<n-1; i++){
			if (seq[i] >= seq[i+1]){
				obligatory_places[i] = true, found++;
				if (i+1 < n-1) obligatory_places[i+1] = true, found++;
				if (i-1 >= 0) obligatory_places[i-1] = true, found++;
				break;
			}
		}
		if (found == 0) printf ("NIE\n");
		else print_result(found, k);
	}

	if (k == 2){
		cur_min_lr[0] = seq[0];
		for (int i=1; i<n; i++) cur_min_lr[i] = std::min(seq[i], cur_min_lr[i-1]);

		cur_max_rl[n-1] = seq[n-1];
		for (int i=n-2; i>=0; i--) cur_max_rl[i] = std::max(seq[i], cur_max_rl[i+1]);

		for (int i=0; i<n-1; i++) {
			if (cur_min_lr[i] >= cur_max_rl[i+1]){
			       	obligatory_places[i] = true, found++;
				break;
			}
		}
		if (found == 0) printf ("NIE\n");
		else print_result(found, k);
	}

	if (k == 3){
		int min_pos = 0, max_pos = n-1;
		for (int i=0; i<n; i++){
			if (seq[i] <= seq[min_pos]) min_pos = i;
		}
		for (int i=n-1; i>=0; i--){
			if (seq[i] >= seq[max_pos]) max_pos = i;
		}

		if (min_pos == 0 && max_pos == n-1) printf ("NIE\n");
		else if (min_pos != 0){
			obligatory_places[min_pos-1] = true, found++;
			if (min_pos != n-1) obligatory_places[min_pos] = true, found++;

			print_result(found, k);
		}
		else if (max_pos != n-1){
			obligatory_places[max_pos] = true, found++;
			if (max_pos != 0) obligatory_places[max_pos-1] = true, found++;

			print_result(found, k);
		}
	}

return 0;}