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

using namespace std;

#define f   first
#define s   second

int sz, compartments;
vector<int> numbers;
vector<int> left_min;
vector<int> right_max;
vector<int> answers;

void Prepare();
bool Solve();

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> sz >> compartments;
    numbers = left_min = right_max = vector<int>(sz);
    answers = vector<int>(compartments - 1);
    for (int i = 0; i < sz; i++) {
        cin >> numbers[i];
    }
    Prepare();
    if (Solve()) {
        cout << "TAK" << endl;
        for (int i = 0; i < answers.size(); i++) {
            cout << answers[i] << " ";
        }
        cout << endl;
    } else {
        cout << "NIE" << endl;
    }
    return 0;
}

void Prepare() {
    left_min[0] = numbers[0];
    for (int i = 1; i < left_min.size(); i++) {
        left_min[i] = min(left_min[i - 1], numbers[i]);
    }
    right_max[numbers.size() - 1] = numbers[numbers.size() - 1];
    for (int i = numbers.size() - 2; i >= 0; i--) {
        right_max[i] = max(right_max[i + 1], numbers[i]);
    }
}

bool Solve() {
    if (compartments == 2) {
        for (int i = 1; i < numbers.size(); i++) {
            if (left_min[i - 1] >= right_max[i]) {
                answers[0] = i - 1;
                return true;
            }
        }
    } else if (compartments == 3) {
        for (int i = 1; i < numbers.size() - 1; i++) {
            if (left_min[i - 1] >= numbers[i] || numbers[i] >= right_max[i + 1]) {
                answers[0] = i;
                answers[1] = i + 1;
                return true;
            }
        }
    } else {
        for (int i = 1; i < numbers.size(); i++) {
            if (numbers[i - 1] >= numbers[i]) {
                if (i == 1) {
                    answers[0] = 1;
                    answers[1] = 2;
                    int iter = 3;
                    for (int i = 2; i < answers.size(); i++) {
                        answers[i] = iter++;
                    }
                } else if (i == numbers.size() - 1) {
                    int iter = 1;
                    for (int i = 0; i < answers.size() - 2; i++) {
                        answers[i] = iter++;
                    }
                    answers[answers.size() - 2] = i - 1;
                    answers[answers.size() - 1] = i;
                } else {
                    cout << i << endl;
                    answers[0] = i - 1;
                    answers[1] = i;
                    answers[2] = i + 1;
                    int iter1 = 3;
                    int iter2 = 1;
                    for (iter1; iter1 < answers.size() && iter2 < i - 1; iter1++, iter2++) {
                        answers[iter1] = iter2;
                    }
                    if (iter1 != answers.size()) {
                        iter2 = i + 2;
                        for (iter1; iter1 < answers.size(); iter1++, iter2++) {
                            answers[iter1] = iter2;
                        }
                    }
                    sort(answers.begin(), answers.end());
                }
                return true;
            }
        }
    }
    return false;
}