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

using namespace std;

template <class iterator>
vector<int> cum_min(iterator data_begin, iterator data_end)
{
    vector<int> cmin(data_end-data_begin);
    auto itcmin=cmin.begin();
    for (auto itdata=data_begin; itdata!=data_end; ++itdata, ++itcmin)
    {
        if (itdata==data_begin)
            *itcmin = *data_begin;
        else
            *itcmin = min(*itdata, *(itcmin-1));
    }
    return cmin;
}

template <class iterator>
vector<int> cum_max(iterator data_begin, iterator data_end)
{
    vector<int> cmax(data_end-data_begin);
    auto itcmax=cmax.begin();
    for (auto itdata=data_begin; itdata!=data_end; ++itdata, ++itcmax)
    {
        if (itdata==data_begin)
            *itcmax = *data_begin;
        else
            *itcmax = max(*itdata, *(itcmax-1));
    }
    return cmax;
}

template <class t>
int znajdz_2nierosnace(vector<t> ciag)
// zwraca index pierwszego z pary nirosnacych elementow lub -1 jesli taka para nie istnieje
{
    for (int ii=0; ii< (int)ciag.size()-1; ii++)
    {
        if (ciag[ii]>=ciag[ii+1])
            return ii;
    }
    return -1;
}


int main()
{
    int n,k;
    cin>>n>>k;

    vector<int> ciag;
    std::copy_n(istream_iterator<int>(std::cin), n, back_inserter(ciag) );

    if (k==2)
    {
        vector<int> cmin_front = cum_min(ciag.begin(), ciag.end());
        vector<int> cmax_back  = cum_max(ciag.rbegin(), ciag.rend());
        reverse(cmax_back.begin(), cmax_back.end());
        for (int ii=0; ii< (int)ciag.size()-1; ii++)
        {
            if (cmin_front[ii] >= cmax_back[ii+1]) // kazdy el. do tego miejsca >= od każdego el. za tym miejscem
            {
                cout<<"TAK"<<endl;
                cout<<ii+1<<endl;
                return 0;
            }
        }
        cout<<"NIE"<<endl;
    }


    else if (k==3)
    {
        uint32_t max_ind = max_element(ciag.begin(), ciag.end()) - ciag.begin() +1; // pierwsze wystapienie maximum
        uint32_t min_ind = ciag.size() - (min_element(ciag.rbegin(), ciag.rend()) - ciag.rbegin()); // ostatnie wystapienie minimum - indeksowane od poczatku!!!
        if (min_ind==1 && max_ind==ciag.size()) // minimum na poczatku i maximum na koncu ciagu - nie da sie podzielic na 3
        {
            cout<<"NIE"<<endl;
            return 0;
        }
        // wybierz maksymalny lub minimanly element jako niezalezny zbior
        pair<int,int> podzialy;
        if(max_ind>1 && max_ind < ciag.size())
            podzialy=make_pair(max_ind-1, max_ind);
        else if(min_ind>1 && min_ind < ciag.size())
            podzialy=make_pair(min_ind-1, min_ind);
        else // minimum na koncu i maximum na poczatku ciagu
            podzialy=make_pair(max_ind, min_ind-1);

        cout<<"TAK"<<endl;
        cout<<podzialy.first<<' '<<podzialy.second<< endl;
    }


    else // k>=4
    {
        // znajdz 2 kolejne elementy w ciagu ktore sa nierosnace - kazdy z tych elementow bedzie 1 podzbiorem
        int ind = znajdz_2nierosnace(ciag);
        if (ind==-1) // ciag jest scisle rosnacy, nie da sie podzielic
        {
            cout<<"NIE"<<endl;
            return 0;
        }

        set<int> podzialy;
        ind++; //indeksowanie od 1
        if (ind==1) // warunek spelniony przez 2 pierwsze elementy
            podzialy.insert({ind, ind+1});
        else if (ind+1 == (int)ciag.size()) // warunek spelniony przez 2 ostatnie elementy
            podzialy.insert({ind-1, ind});
        else
            podzialy.insert({ind-1, ind, ind+1});


        // dodaj brkujacą liczbę podzialow w dowolnych miejscach
        int nowyPodzial = 1;
        while ((int)podzialy.size()<k-1)
        {
            podzialy.insert(nowyPodzial);
            nowyPodzial++;
        }
        cout<<"TAK"<<endl;
        for(auto it=podzialy.begin(); it!=podzialy.end(); ++it)
            cout<<*it<<' ';
        cout<<endl;
    }





    return 0;
}