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

#define ll long long

using namespace std;

#define MAYBE_EOL "\n"

int main() {
    std::ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    vector<ll> A(n);
    for(ll i = 0; i < n; i++) cin >> A[i];
    if(k == 2) {
        multiset<ll> S(A.begin(), A.end());
        ll mmin = A[0];
        S.erase(S.find(mmin));
        for(ll i = 1; S.size() > 0; i++) {
            if(mmin >= *S.rbegin()) {
                cout << "TAK" << MAYBE_EOL;
#ifndef NO_NUMS
                cout << i << MAYBE_EOL;
#endif
                return 0;
            }
            S.erase(S.find(A[i]));
            mmin = min(mmin, A[i]);
        }
        cout << "NIE" << MAYBE_EOL;
        return 0;
    } else if(k == 3) {
        ll mmin = A[0];
        for(ll i = 1; i < n; i++) {
            if(mmin >= A[i]) {
                cout << "TAK" << MAYBE_EOL;
#ifndef NO_NUMS
                if(i == n - 1)
                    cout << i - 1 << " " << i << MAYBE_EOL;
                else
                    cout << i << " " << i + 1 << MAYBE_EOL;
#endif
                return 0;
            }
            mmin = min(mmin, A[i]);
        }
        ll mmax = A[n - 1];
        for(ll i = n - 2; i >= 0; i--) {
            if(mmax <= A[i]) {
                cout << "TAK" << MAYBE_EOL;
#ifndef NO_NUMS
                if(i == 0)
                    cout << i + 1 << " " << i + 2 << MAYBE_EOL;
                else
                    cout << i << " " << i + 1 << MAYBE_EOL;
#endif
                return 0;
            }
            mmax = max(mmax, A[i]);
        }
        cout << "NIE" << MAYBE_EOL;
        return 0;
    } else {
        ll split = -1;
        for(ll i = 0; i < n - 1; i++)
            if(A[i] >= A[i + 1]) {
                split = i;
                break;
            }
        if(split == -1) {
            cout << "NIE" << MAYBE_EOL;
            return 0;
        } else {
            cout << "TAK" << MAYBE_EOL;
#ifndef NO_NUMS
            ll additional = k - 4;
            if(split + 2 == n)
                additional += 1;
            if(split == 0)
                additional += 1;
            for(ll i = 0; i < n - 1; i++)
                if(i == split - 1 || i == split || i == split + 1) {
                    cout << i + 1 << " ";
                } else if(additional > 0) {
                    cout << i + 1 << " ";
                    additional -= 1;
                }
#endif
            return 0;
        }
    }
    return 0;
}