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
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, b, e) for(int i = (b); i < (e); i++)
#define TRAV(x, v) for(auto &x: v)
#define PB push_back
#define SZ(x) ((int)x.size())
#define X first
#define Y second

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;

int n;

void wypisz(vi chce, int k) {
    vi corr;
    TRAV(x, chce) if(0 <= x && x < n - 1) corr.PB(x);
    k -= SZ(corr) + 1;
    cout << "TAK\n";
    FOR(i, 0, n) {
        if(find(corr.begin(), corr.end(), i) != corr.end()) cout << i + 1 << ' ';
        else if(k > 0) {
            cout << i + 1 << ' ';
            k--;
        }
    }
    cout << '\n';
}

void solve2(vi vec) {
    vi sufMax(SZ(vec) + 1);
    for(int i = SZ(vec) - 1; i >= 0; i--) sufMax[i] = max(sufMax[i + 1], vec[i]);
    int prefMin = INF;
    FOR(i, 0, SZ(vec) - 1) {
        prefMin = min(prefMin, vec[i]);
        if(prefMin >= sufMax[i + 1]) return wypisz({i}, 2);
    }
    cout << "NIE\n";
}

void solve3(vi vec) {
    int mini = *min_element(vec.begin(), vec.end());
    int miniPos = find(vec.begin() + 1, vec.end(), mini) - vec.begin();
    if(miniPos != SZ(vec)) return wypisz({miniPos - 1, miniPos}, 3);
    int maxi = *max_element(vec.begin(), vec.end());
    int maxiPos = find(vec.begin(), vec.end() - 1, maxi) - vec.begin();
    if(maxiPos != SZ(vec) - 1) return wypisz({maxiPos - 1, maxiPos}, 3);
    cout << "NIE\n";
}

void solve4(vi vec, int k) {
    FOR(i, 0, SZ(vec) - 1) if(vec[i] >= vec[i + 1]) return wypisz({i - 1, i, i + 1}, k);
    cout << "NIE\n";
}

void solve() {
    int k;
    cin >> n >> k;
    vi vec(n);
    TRAV(x, vec) cin >> x;
    if(k == 2) solve2(vec);
    if(k == 3) solve3(vec);
    if(k >= 4) solve4(vec, k);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // int tt; cin >> tt;
    // FOR(te, 0, tt) {
    //     // cout << "Case #" << te + 1 << ": ";
    //     solve();
    // }
    solve();
    return 0;
}