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 #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pi; typedef vector vi; const int S = 1e6 + 7; const int mod = 1e9 + 7; int tab[S], n, m, k, pref[S], suf[S]; // inject here bool is_strictly_increasing(){ for (int i = 1; i < n; i ++){ if (! (tab[i] < tab[i + 1])){ return false; } } return true; } void check_for_k3(int pos){ if (pref[pos - 1] < tab[pos] && tab[pos] < suf[pos + 1]) return; cout << "TAK\n"; cout << pos - 1 << " " << pos << endl; exit(0); } void solve(){ cin >> n >> k; for (int i = 1; i <= n; i ++){ cin >> tab[i]; } if (is_strictly_increasing()){ cout << "NIE\n"; return; } else if (k >= 4){ cout << "TAK\n"; for (int i = 2; i <= n; i ++){ if (tab[i - 1] >= tab[i]){ vector mid_to_left = {1, i - 2}; vector mid_to_right = {1, n - i}; if (mid_to_left.back() == 0) mid_to_left.pop_back(); if (mid_to_right.back() == 0) mid_to_right.pop_back(); while (mid_to_left.size() + mid_to_right.size() < k){ if (mid_to_left.back() > 1){ int buffer = mid_to_left.back(); mid_to_left.back() = 1; mid_to_left.push_back(buffer - 1); } else if (mid_to_right.back() > 1){ int buffer = mid_to_right.back(); mid_to_right.back() = 1; mid_to_right.push_back(buffer - 1); } } reverse(mid_to_left.begin(), mid_to_left.end()); for (auto e : mid_to_right){ mid_to_left.push_back(e); } auto X = mid_to_left; int sum = 0; for (int i = 0; i < (int) X.size() - 1; i ++){ sum += X[i]; cout << sum << " "; } cout << endl; return; } } } else { pref[0] = mod; suf[n + 1] = 0; for (int i = 1; i <= n; i ++){ pref[i] = min(pref[i - 1], tab[i]); } for (int i = n; i >= 1; i --){ suf[i] = max(suf[i + 1], tab[i]); } if (k == 2){ for (int i = 2; i <= n; i ++){ if (pref[i - 1] >= suf[i]){ cout << "TAK\n"; cout << i - 1 << "\n"; return; } } } else { pi min_p = {tab[2], 2}, max_p = {tab[2], 2}; for (int i = 3; i < n; i ++){ min_p = min(min_p, {tab[i], i}); max_p = max(max_p, {tab[i], i}); } // cout << min_p.first << " " << min_p.second << endl; check_for_k3(min_p.second); check_for_k3(max_p.second); } cout << "NIE\n"; } } int main(){ ios_base::sync_with_stdio(0); int t = 1; //cin >> t; while (t --) solve(); return 0; }