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
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
    int n,k; cin >> n >> k;
    vector<int> A(n);
    for(int i=0;i<n;i++)cin >> A[i];
    if(k==2){
        vector<int> p(n+1,1e9),s(n+1,-1*(1e9));
        // pref od i+1 to najmiejszy element [0,i]
        // suf od i+1 to najwieksy element w przedziale [i+1,n-1]
        for(int i=1;i<=n;i++)p[i] = min(p[i-1],A[i-1]);
        for(int i=n-1;i>=0;i--)s[i] = max(s[i+1], A[i]);
        // for(int i=0;i<n+1;i++) cout << p[i] <<  ' ';
        // cout << '\n';
        // for(int i=0;i<n+1;i++) cout << s[i] <<  ' ';
        // cout << '\n';
        bool git = false;
        for(int i=0;i<n-1;i++){
            if(p[i+1] >= s[i+1]){
                cout <<  "TAK\n" << i+1 << '\n';
                git = true;
                break;
            }
        }
        if(!git) cout << "NIE\n";
    }
    else if(k==3){
        if(A[0] >= A[n-1]){
            cout << "TAK\n" << 1 << ' ' << n-1 << '\n';
        }
        else{
            for(int i=1;i<n-1;i++){
                if(A[i] <= A[0]){
                    cout << "TAK\n" << i << ' ' <<  i+1 << '\n';
                    return 0;
                }
            }
            
            for(int i=n-2;i>0;i--){
                if(A[i] >= A[n-1]){
                    cout << "TAK\n" << i << ' ' <<  i+1 << '\n';
                    return 0;
                }
            }
            cout << "NIE\n";
        }
    }
    else{
        bool git = false;
        vector<int> rez(k-1);
        for(int i=0;i<k-1;i++)rez[i] = i+1;
        for(int i=1;i<n;i++){
            if(A[i] <= A[i-1]){
                git = true;
                if(i+1>k && i+1 != n){
                    rez[k-4] = i-1;
                    rez[k-3] = i;
                    rez[k-2] = i+1;
                }
                else if(i+1>k){
                    rez[k-3] = i-1;
                    rez[k-2] = i    ;
                }
                break;
            }
        }
        if(git){
            cout << "TAK\n";
            for(int i=0;i<rez.size();i++)cout << rez[i] << ' ';
            cout << '\n';
        }
        else cout << "NIE\n";
    }
}