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
#include<bits/stdc++.h>
using namespace std;
const int MAXX=1e5*5+10; 
int tab[MAXX];
int minn[MAXX];
int maxx[MAXX];
int patyczki[MAXX];
int main(){
    int n, k;
    cin>>n>>k; 
    k--;
    for(int i=1;i<=n;i++){
        cin>>tab[i];
    }
    memset(minn, 1000000005, sizeof minn);
    for(int i=1;i<=n;i++){
        minn[i]=min(minn[i-1], tab[i]);
    }
    for(int i=n;i>0;i--){
        maxx[i]=max(maxx[i+1], tab[i]);
    }
    if(k>=3){
        int ok=0;
        int x=k;
        for(int i=2;i<=n;i++){
            if(ok==1)break;
            if(tab[i]<=tab[i-1]){
                if(i-2==0)x++;
                else patyczki[i-2]=1; 
                patyczki[i-1]=1;
                if(i==n)x++;
                else patyczki[i]=1;
                x-=3;
                ok=1;
            }
        }
        if(x>0){
            for(int i=1;i<=n;i++){
                if(x==0)break;
                if(patyczki[i]==0){patyczki[i]=1;x--;}
            }
        }
        if(ok==0){cout<<"NIE\n";return 0;}
        if(ok==1){cout<<"TAK\n";}
        for(int i=1;i<=n;i++){
            if(patyczki[i]==1)cout<<i<<" ";
        }
        return 0;
    }
    int ok=0;
    int x=k;
    if(minn[1]>=maxx[2]&&k<=2){patyczki[1]=1;x--;ok=1;}
    //if(minn[n-1]>=maxx[n]){patyczki[n]=1;x--;ok=1}
    for(int i=2;i<n;i++){
        if(ok==1)break;
        if(k==1){
            if(minn[i]>=maxx[i+1]){patyczki[i]=1;x--;ok=1;}
        }   
        if(k==2){
            //cout<<minn[i-1]<<" "<<tab[i]<<" "<<maxx[i+1]<<" "<<i<<"\n";
            if(minn[i-1]>=tab[i]||tab[i]>=maxx[i+1]){patyczki[i]=1;patyczki[i-1]=1;x-=2;ok=1;}
        }    
    }
    if(ok==0){cout<<"NIE\n";return 0;}
    cout<<"TAK\n";
    for(int i=1;i<=n;i++){
        if(x==0)break;
        if(patyczki[i]==0){patyczki[i]=1;x--;}
    }
    for(int i=1;i<=n;i++){
        if(patyczki[i]==1)cout<<i<<" ";
    }
    return 0;
}