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
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdint>
#include <bitset>
using namespace std;


void solve2(int n, int k, const vector<int> &a){
    vector <int> amin(n); //amin[i] = min(a[0]..a[i])
    vector <int> amax(n); //amax[i] = max(a[i+1]..a[n-1])

    amin[0]=a[0];
    for (int i=1; i<n; i++){
        amin[i]=min(amin[i-1], a[i]);
    }
    amax[n-2]=a[n-1];
    for (int i=n-3; i>=0; i--){
        amax[i]=max(amax[i+1], a[i+1]);
    }

    for (int i=0; i<n-1; i++){
        if (amin[i] >= amax[i]){
            cout<<"TAK"<<endl;

            cout<<i+1<<endl;
            return;
        }
    }
    cout<<"NIE"<<endl;
}

void solve3(int n, int k, const vector<int> &a){

    auto mM = minmax_element(begin(a)+1, end(a)-1);
    auto m = mM.first;
    auto M = mM.second;

    if (*M>=a.back()){
        cout<<"TAK"<<endl;
        cout<< M-begin(a)<<" "<< M-begin(a)+1<<endl;
       }
    else if(*m<=a.front()) {
        cout<<"TAK"<<endl;
        cout<< m-begin(a)<<" "<< m-begin(a)+1<<endl;
    }else{
        cout<<"NIE"<<endl;
    }
}

void solve4p(int n, int k, const vector<int> &a){
    auto it = is_sorted_until(begin(a), end(a),less_equal<int>());

    k--;//liczba przerwan
    if (it==end(a)){//ciąg posortowany, nic nie zrobimy
        cout<<"NIE"<<endl;
    }else{
        cout<<"TAK"<<endl;
        int limit = 3;
        if (it==prev(end(a))) limit=2;
        int pre_it = it-begin(a)-1;
        int i=1;
        for ( ; (i<pre_it) && (k>limit); i++){
            cout<<i<<" ";
            k--;
        }
        for (i=max<int>(pre_it,1); k>0; k--,i++){
            cout<<i<<" ";
        }
        cout<<endl;
    }
}



int main()
{
    int n,k;
    vector<int> a;
    cin>>n>>k;
    a.reserve(n);

    copy_n(istream_iterator<int>(cin),n , back_inserter(a));


    if (k==2) solve2(n,k,a);
    if (k==3) solve3(n,k,a);
    if (k>=4) solve4p(n,k,a);

}