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
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5+5;
int arr[mxn];
int suffmax[mxn];
int prefmin[mxn];
vector<int> range_ends;

int main() {

      int n, k;
      scanf("%d%d",&n,&k);
      for(int i = 0; i < n; ++i){
            scanf("%d",&arr[i]);
      }
      bool win = false;
      if(k > 2){

            k--;
            // now k becomes the lines, not the ranges

            for(int i = n - 1; i >= 0; --i){
                  suffmax[i] = max(suffmax[i+1],arr[i]);
            }

           /* cout<<"suffmax: "<<endl;
            for (int i = 0; i < n; ++i) {
                  cout<<suffmax[i]<<" ";
            }*/

            suffmax[n] = -1;

            int sel1 = -1, sel2 = -1;

            for(int i = n - 1; i >= 0; --i){

                  if(suffmax[i+1] == -1) continue;

                  if(suffmax[i+1] <= arr[i]){
                        win = true;
                       // cout<<"found a win defining one at "<<i<<endl;
                        range_ends.push_back(i + 1);
                        sel1 = i + 1;
                        k--;

                        if(i-1 != 0){
                              range_ends.push_back(i-1  + 1);
                              k--;
                              sel2 = i-1 + 1;
                        }
                        break;
                  }
            }

            if(!win){
                  printf("NIE");
                  return 0;
            }

            for(int i = 0; i < n; ++i){
                  if(k == 0){
                        // no more lines to insert
                        break;
                  }
                  if(i+1 != sel1 && i+1 != sel2){
                        // if it is not any of the 2 winning lines we selected before
                        range_ends.push_back(i+1);
                        k--;
                  }
            }

      }else if(k == 2){

            // check if its non-increasing, if so - win guaranteed, put the line wherever
            bool noninc = true;
            for(int i = 0; i < n - 1; ++i){
                  if(arr[i] < arr[i+1]){
                        noninc = false;
                        break;
                  }
            }

            if(noninc){
                  //cout<<"its nonincreasing, so free win\n";
                  range_ends.push_back(1);
            }else{
                  //cout<<"its some rand shit with k=2 so searching for 1 wall\n";
                  for(int i = n - 1; i >= 0; --i){
                        suffmax[i] = max(suffmax[i+1],arr[i]);
                  }
                  for(int i = 0; i < n ; ++i){
                        if(i==0) prefmin[i] = arr[i];
                        else prefmin[i] = min(prefmin[i-1],arr[i]);
                  }


                  /*cout<<"prefmin: "<<endl;
                  for (int i = 0; i < n; ++i) {
                        cout<<prefmin[i]<<" ";
                  }*/

                  win = true;

                  for(int i = 0; i < n - 1; ++i){
                        if(prefmin[i] < suffmax[i+1]){
                             // cout<<"found position that works unf, at "<<i<<endl;
                              win = false;
                              break;
                        }
                  }

                  if(!win){
                        printf("NIE");
                        return 0;
                  }


            }

      }

      printf("TAK\n");
      sort(range_ends.begin(), range_ends.end());
      for(auto& a : range_ends){
            printf("%d ", a);
      }

      return 0;
}