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
#include <cstdio>
#include <algorithm>

int tab[510000];
int lmin[510000];
int rmax[510000];

int main() {
    int N, K;
    scanf("%d %d", &N, &K);

    for (int i=1; i<=N; ++i) {
        int v;
        scanf("%d", &v);
        tab[i] = v;
    }

    //czy da sie podzielic ze nie ma rosnacego ciagu?
    if (K==2) {
        //min(left) >= max(right)
        lmin[1] = tab[1];
        for (int i=2; i<=N; ++i) {
            lmin[i] = std::min(lmin[i-1], tab[i]);
        }

        rmax[N] = tab[N];
        for (int i=N-1; i>=1; --i) {
            rmax[i] = std::max(rmax[i+1], tab[i]);
        }

        for (int i=1; i<N; ++i) {
            if (lmin[i] >= rmax[i+1]) {
                printf("TAK\n");
                printf("%d ", i);
                return 0;
            }
        }

        printf("NIE\n");
    } else if (K==3) {
        //minimalny nie po lewej stronie lub maksymalny nie po prawej
        for (int i=2; i<N; ++i) {
            if (tab[i]<=tab[1]) {
                printf("TAK\n");
                printf("%d %d ", i-1, i);
                return 0;
            }
        }

        for (int i=N-1; i>1; --i) {
            if (tab[i]>=tab[N]) {
                printf("TAK\n");
                printf("%d %d ", i-1, i);
                return 0;
            }
        }

        printf("NIE\n");
    } else {
        //wystarczy ze jest sytuacja ze kolejny element mniejszy lub rowny poprzedniemu
        for (int i=2; i<=N; ++i) {
            if (tab[i] <= tab[i-1]) {
                printf("TAK\n");
                int b = ((i-2>0)?(i-2):(i-1));
                int cnt = N-b;
                int mis = K-1-cnt;

                for (int j=1;j<=mis;++j) {
                    printf("%d ", j);
                }

                for (int j=b; j-b+1<=cnt && j-b+1<K; j++) {
                    printf("%d ", j);
                }

                return 0;
            }
        }

        printf("NIE\n");
    }

    //jak dlugosc 3 to:
        //jesli minimalny nie po lewej stronie lub maksymalny nie po prawej to TAK

    return 0;
}