#include <bits/stdc++.h> // #define MULTIPLE_TESTS // #define ENDLESS_TESTS #define TIME_LIMIT 2 // #define MEMORY_LIMIT 512 // #define ONLY_YES using namespace std; // Cases: // (1) k = 2 [ab] // Single separation point. // Lowest in [A] must be >= than highest in [B]. // (2) k = 3 [ab]c // For any [B] that works, we can reduce it to its first element. // Highest in [A] >= value of [B]. // (-) k = 3 a[bc] // Same as (2). // (3) k = 3 [a]b[c] // For any [A] that works, we can reduce it to its first element. // For any [C] that works, we can reduce it to its last element. // Maybe this is never needed? // (4) k >= 4 // For any sequence: // a) it is strictly increasing, so no partition will be a solution. // b) it is not strictly increasing, so it has two neighbouring elements are not strictly increasing. // These two elements can always be turned into regions with k >= 4. auto compute_low(const vector<int> &data) { const int n = data.size(); vector<int> low(n); low[0] = data[0]; for(int i = 1; i < n; ++i) { low[i] = std::min(low[i-1], data[i]); } return low; } auto compute_high(const vector<int> &data) { const int n = data.size(); vector<int> high(n); high[n-1] = data[n-1]; for(int i = n-2; i >= 0; --i) { high[i] = std::max(high[i+1], data[i]); } return high; } void no() { cout << "NIE\n"; } template<typename ...T> void yes(T ...vals) { cout << "TAK\n"; #ifndef ONLY_YES ((cout << vals+1 << ' '), ...); cout << '\n'; #endif } void solve2(const vector<int> &data) { const int n = data.size(); const auto high = compute_high(data); const auto low = compute_low(data); for (int mid = 1; mid < n; ++mid) { // Case (1) if (low[mid-1] >= high[mid]) { return yes(mid-1); } } no(); } void solve3(const vector<int> &data) { const int n = data.size(); const auto high = compute_high(data); const auto low = compute_low(data); // Case (3) if (data[0] >= data[n-1]) { return yes(0, n-2); } for (int mid = 1; mid < n-1; ++mid) { // Case (2) [ab]c if (low[mid-1] >= data[mid]) { return yes(mid-1, mid); } // Case (2) a[bc] if (data[mid] >= high[mid+1]) { return yes(mid-1, mid); } } no(); } void solve4(const vector<int> &data, const int k) { const int n = data.size(); for (int first = 0; first < n-1; ++first) { if (data[first] >= data[first+1]) { cout << "TAK\n"; #ifndef ONLY_YES const int print_first = std::max(0, first - (k-3) - (first == n-2 ? 1 : 0)); const int print_last = print_first + k - 1; for (int i = print_first; i < print_last; ++i) { cout << i+1 << ' '; } cout << '\n'; #endif return; } } no(); } void test() { int n, k; cin >> n >> k; vector<int> data(n); for (auto &v : data) { cin >> v; } switch(k) { case 2: return solve2(data); case 3: return solve3(data); default: return solve4(data, k); } } int main() { #ifndef CONTEST_WORKSPACE std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); #endif #ifdef ENDLESS_TESTS while(!(cin >> std::ws).eof()) test(); #else int T = 0; #ifdef MULTIPLE_TESTS cin >> T; #else T = 1; #endif while (T --> 0) test(); #endif return 0; }
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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | #include <bits/stdc++.h> // #define MULTIPLE_TESTS // #define ENDLESS_TESTS #define TIME_LIMIT 2 // #define MEMORY_LIMIT 512 // #define ONLY_YES using namespace std; // Cases: // (1) k = 2 [ab] // Single separation point. // Lowest in [A] must be >= than highest in [B]. // (2) k = 3 [ab]c // For any [B] that works, we can reduce it to its first element. // Highest in [A] >= value of [B]. // (-) k = 3 a[bc] // Same as (2). // (3) k = 3 [a]b[c] // For any [A] that works, we can reduce it to its first element. // For any [C] that works, we can reduce it to its last element. // Maybe this is never needed? // (4) k >= 4 // For any sequence: // a) it is strictly increasing, so no partition will be a solution. // b) it is not strictly increasing, so it has two neighbouring elements are not strictly increasing. // These two elements can always be turned into regions with k >= 4. auto compute_low(const vector<int> &data) { const int n = data.size(); vector<int> low(n); low[0] = data[0]; for(int i = 1; i < n; ++i) { low[i] = std::min(low[i-1], data[i]); } return low; } auto compute_high(const vector<int> &data) { const int n = data.size(); vector<int> high(n); high[n-1] = data[n-1]; for(int i = n-2; i >= 0; --i) { high[i] = std::max(high[i+1], data[i]); } return high; } void no() { cout << "NIE\n"; } template<typename ...T> void yes(T ...vals) { cout << "TAK\n"; #ifndef ONLY_YES ((cout << vals+1 << ' '), ...); cout << '\n'; #endif } void solve2(const vector<int> &data) { const int n = data.size(); const auto high = compute_high(data); const auto low = compute_low(data); for (int mid = 1; mid < n; ++mid) { // Case (1) if (low[mid-1] >= high[mid]) { return yes(mid-1); } } no(); } void solve3(const vector<int> &data) { const int n = data.size(); const auto high = compute_high(data); const auto low = compute_low(data); // Case (3) if (data[0] >= data[n-1]) { return yes(0, n-2); } for (int mid = 1; mid < n-1; ++mid) { // Case (2) [ab]c if (low[mid-1] >= data[mid]) { return yes(mid-1, mid); } // Case (2) a[bc] if (data[mid] >= high[mid+1]) { return yes(mid-1, mid); } } no(); } void solve4(const vector<int> &data, const int k) { const int n = data.size(); for (int first = 0; first < n-1; ++first) { if (data[first] >= data[first+1]) { cout << "TAK\n"; #ifndef ONLY_YES const int print_first = std::max(0, first - (k-3) - (first == n-2 ? 1 : 0)); const int print_last = print_first + k - 1; for (int i = print_first; i < print_last; ++i) { cout << i+1 << ' '; } cout << '\n'; #endif return; } } no(); } void test() { int n, k; cin >> n >> k; vector<int> data(n); for (auto &v : data) { cin >> v; } switch(k) { case 2: return solve2(data); case 3: return solve3(data); default: return solve4(data, k); } } int main() { #ifndef CONTEST_WORKSPACE std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); #endif #ifdef ENDLESS_TESTS while(!(cin >> std::ws).eof()) test(); #else int T = 0; #ifdef MULTIPLE_TESTS cin >> T; #else T = 1; #endif while (T --> 0) test(); #endif return 0; } |