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 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); unsigned n, k, v; cin >> n; cin >> k; vector ns; for (auto i = 0; i < n; i++) { cin >> v; ns.push_back(v); } if (k == 2) { // min of the left part must be >= max of the right part at some point vector minimums; minimums.push_back(ns[0]); for (auto i = 1; i < ns.size(); i++) { minimums.push_back(min(minimums[i - 1], ns[i])); } unsigned maximum = ns[ns.size() - 1]; bool found = false; unsigned solution = 0; for (auto i = (long) ns.size() - 2; i >= 0; i--) { if (minimums[i] >= maximum) { found = true; solution = i + 1; break; } maximum = max(maximum, ns[i]); } cout << (found ? "TAK" : "NIE") << endl; if (found) { cout << solution << endl; } } else if (k == 3) { unsigned minimum = ns[0]; bool found = false; unsigned lower = 0; unsigned upper = 0; for (auto i = 1; i < ns.size() - 1; i++) { if (ns[i] <= minimum) { found = true; lower = i; upper = i + 1; break; } minimum = min(minimum, ns[i]); } if (!found) { unsigned maximum = ns[ns.size() - 1]; for (auto i = ns.size() - 2; i > 0; i--) { if (ns[i] >= maximum) { found = true; lower = i; upper = i + 1; } maximum = max(maximum, ns[i]); } } cout << (found ? "TAK" : "NIE") << endl; if (found) { cout << lower << " " << upper << endl; } } else { // there must be such a pair of indexes (i,j) that i < j and ns[i] >= ns[j]. unsigned maximum = ns[0]; unsigned maximum_lower = 0; unsigned maximum_upper = 1; bool found = false; unsigned lower = 0; unsigned upper = 0; for (auto i = 1; i <= ns.size() - 1; i++) { if (ns[i] <= maximum) { found = true; lower = i; upper = i + 1; break; } if (ns[i] >= maximum) { maximum = ns[i]; maximum_lower = i; maximum_upper = i + 1; } } set poses; if (maximum_lower != 0) { poses.insert(maximum_lower); } if (upper != ns.size() - 1) { poses.insert(upper); } poses.insert(maximum_upper); poses.insert(lower); unsigned idx = 1; while (poses.size() != k - 1) { poses.insert(idx); idx += 1; } cout << (found ? "TAK" : "NIE") << endl; if (found) { for (const auto &pos: poses) { cout << pos << " " << endl; } } } return 0; }