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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#pragma GCC optimize("Ofast")

#include <iostream>

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n; std::cin >> n;
	int k; std::cin >> k;
	int* arr = new int[n];
	for(int i = 0; i < n; i++)
		std::cin >> arr[i];

	//simplest case
	/*
		find the first value y that is smaller than previous one x
		create 4 regions
		before x, x, y, after y
		it is 100% impossible to create increasing sequence because y is smaller than x 
		else if every single one is greater than previous then it is always possible to create increasing sequence
	
		now we might need to create more regions out of before x and after x but it is not that important, any division will work
	*/
	if(k >= 4)
	{
		int y_location = -1;
		for(int i = 1; i < n; i++)
		{
			if(arr[i] <= arr[i - 1])
			{
				y_location = i;
				break;
			}
		}
		
		if(y_location == -1)
		{
			std::cout << "NIE\n";
			goto end;
		}
		std::cout << "TAK\n";
		//now we have y_location and from that we have x_location
		const int x_location = y_location - 1;
		//k now represents how many more regions we have to add
		k -= 3;
		if(y_location == n - 1)
			k++;
		if(x_location == 0)
			k++;
		
		const int min = k < x_location ? k : x_location;
		for(int i = 1; i <= min; i++)
		{
			std::cout << i << ' ';
		}
		std::cout << x_location  + 1 << ' ';
		if(y_location != n - 1 )
			std::cout << y_location + 1 << ' ';
		
		if(k > min)
		{
			const int max = y_location + 1 + k;
			for(int i = y_location + 2; i < max; i++)
			{
				std::cout << i << ' ';
			}
		}
		std::cout << '\n';
	}
	else if(k == 2)
	{
		//here the only possibility is that there are two regions 
		//first one contains elements that are not smaller than second one
		
		//two arrays denoting max and min up to certain point
		//min denotes min value from 0 up to i 
		//max denotes max value from i to n - 1
		int* min = new int[n];
		int* max = new int[n];

		int min_val = arr[0];
		min[0] = arr[0];
		for(int i = 1; i < n; i++)
		{
			if(arr[i] < min_val)
				min_val = arr[i];

			min[i] = min_val;
		}
		int max_val = arr[n - 1];
		max[n - 1]  = arr[n - 1];
		for(int i = n - 2; i >= 0; i--)
		{
			if(arr[i] > max_val)
				max_val = arr[i];

			max[i] = max_val;
		}

		//if and only if there exists index x such that 
		//min[x - 1] > max[x]
		//then there is a solution
		//otherwise there is no
		int index = -1;
		for(int i = 1; i < n; i++)
		{
			if(min[i - 1] >= max[i])
			{
				index = i;
				break;
			}
		}
		
		if(index == -1)
			std::cout << "NIE\n";
		else 
			std::cout << "TAK\n" << index << '\n';
			
		delete[] min;
		delete[] max;
	}
	else //k == 3
	{
		//find the biggest, if there is, then there are 3 regions
		//before biggest, biggest, after biggest
		//such a thing will work if the biggest one is not last
		//this should catch *most* inputs
		int max_val = arr[0];
		int max_pos = 1;
		for(int i = 1; i < n; i++)
		{
			if(arr[i] > max_val)
			{
				max_val = arr[i];
				max_pos = i + 1;
			}
		}
		if(max_pos == 1)
		{
			std::cout << "TAK\n";
			std::cout << "1 2\n";
			goto end;;
		}
		if(max_pos != n)
		{
			std::cout << "TAK\n";
			std::cout << max_pos - 1 << ' ' << max_pos << '\n';

			goto end;
		}
		//if biggest is the last one we know we HAVE TO cut the last part
		//so we find first element X from the left that is not bigger than everything from the left and divide it into three regions
		//before X, X, after X
		const int min_val = arr[0];
		int pos = -1;
		for(int i = 1; i < n; i++)
		{
			if(arr[i] <= min_val)
			{
				pos = i + 1;
				break;
			}
		}
		if(pos == -1)
			std::cout << "NIE\n";
		else
			std::cout << "TAK\n" << pos - 1 << ' ' << pos << '\n';
	}


end:
	delete[] arr;
}