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
#include <bits/stdc++.h>
using namespace std;

// zadanie do którego rozwiązanie da się napisać w 15 minut, ale debugowanie go zajmuje 3 godziny

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k; cin >> n >> k;
    vector<int> a(n);
    for(auto &&e : a) cin >> e;
    if(a.front() >= a.back()) {
        if(k == 2) {
            // sprawdzamy czy da się by min K1 ≥ max K2
            vector<int> mini(n), maxi(n);
            mini[0] = a[0]; for(int i = 1; i < n; ++i) mini[i] = min(mini[i-1], a[i]);
            maxi[n-1] = a[n-1]; for(int i = n-2; i >= 0; --i) maxi[i] = max(maxi[i+1], a[i]);

            for(int i = 1; i < n; ++i) { // (0..i-1) (i..n-1)
                if(mini[i-1] >= maxi[i]) {
                    cout << "TAK\n" << i << '\n';
                    return 0;
                }
            }
            cout << "NIE\n";
        } else {
            // izolujemy front i back, resztę dzielimy jakkolwiek
            cout << "TAK\n";
            cout << "1 ";
            for(int i = 2; i < k-1; ++i) cout << i << ' ';
            cout << n-1 << '\n';
        }
    } else {
        if(k == 2) {
            // nie da się, bo może wybrać front i back
            cout << "NIE\n"; return 0;
        } else if(k == 3) {
            // izolujemy element spoza (front, back)
            int miniv = INT_MAX, mini = -1, maxiv = INT_MIN, maxi = -1;
            for(int i = 1; i < n-1; ++i) {
                if(miniv > a[i]) miniv = a[i], mini = i;
                if(maxiv < a[i]) maxiv = a[i], maxi = i;
            }
            if(miniv <= a.front()) {
                cout << "TAK\n" << mini << ' ' << mini+1 << '\n';
                return 0;
            }
            if(maxiv >= a.back()) {
                cout << "TAK\n" << maxi << ' ' << maxi+1 << '\n';
                return 0;
            }
            cout << "NIE\n";
        } else {
            // izolujemy dwa elementy słabo malejące, resztę dzielimy jakkolwiek
            int i;
            for(i = 0; i < n-1 && a[i] < a[i+1]; ++i);
            if(i == n-1) { cout << "NIE\n"; return 0; }
            cout << "TAK\n";
            if(i+2 >= n) i -= n-i-1;
            int iniewpoczatku = (i+2 < k-1) ? 0 : 3; // musi być i, i+1 i i+2
            for(int j = 1; j < k - iniewpoczatku; ++j) // 1 .. k - 1
                cout << j << ' ';
            if(iniewpoczatku != 0) cout << i << ' ' << i+1 << ' ' << i+2;
            cout << '\n';
        }
    }
}