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
84
85
86
87
88
89
90
91
92
93
94
95
// Kacper Orszulak
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
	int n, k;
	scanf("%d %d", &n, &k);
	vector<int> arr(n), pref_min(n), suffix_max(n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &arr[i]);
		pref_min[i] = arr[i];
		if (i > 0)
			pref_min[i] = min(pref_min[i], pref_min[i-1]);
	}
	for (int i = n-1; i >= 0; --i) {
		suffix_max[i] = arr[i];
		if (i < n-1)
			suffix_max[i] = max(suffix_max[i], suffix_max[i+1]);
	}

	if (k == 2) {
		bool possible = false;
		int i = 0;
		for (; i < n-1; ++i) {
			if (pref_min[i] >= suffix_max[i+1]) {
				possible = true;
				break;
			}
		}
		if (possible) {
			printf("TAK\n%d\n", i+1);
		} else {
			printf("NIE\n");
		}
	} else if (k == 3) {
		bool possible = false;
		int i = 0;
		for (; i < n-2; ++i) {
			if (pref_min[i] >= arr[i+1]) {
				possible = true;
				break;
			}
			if (arr[i+1] >= suffix_max[i+2]) {
				possible = true;
				break;
			}
		}
		if (possible) {
			printf("TAK\n%d %d\n", i+1, i+1 +1);
		} else {
			printf("NIE\n");
		}

	} else if (k >= 4) {
		bool possible = false;
		int i = 0;
		for (; i < n-1; ++i) {
			if (arr[i] >= arr[i+1]) {
				possible = true;
				break;
			}
		}

		if (!possible) {
			printf("NIE\n");
		} else {
			vector<int> result;
			if (i > 0) result.push_back(i-1 +1);
			result.push_back(i +1);
			if (i != n-2) result.push_back(i+1 +1);

			k -= result.size()+1;
			int j = 0;
			while (k > 0 && j < n-1) {
				if (j == i-1 || j == i || j == i+1) {
					++j;
					continue;
				}
				result.push_back(j +1);
				++j;
				--k;
			}
			sort(result.begin(), result.end());

			printf("TAK\n");
			for (const int e : result)
				printf("%d ", e);
			printf("\n");
		}
	}

	return 0;
}