#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define st first #define nd second #define pb push_back #define mp make_pair #define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;++i) #define all(a) a.begin(),a.end() #define sz(x) (int)(x).size() const int mxN = 5e5+7, INF = 1e9+7; int a[mxN], n, k; int mnp[mxN], mxs[mxN]; void solve(){ rep(i,1,n-1) if(a[i] >= a[i+1]){ cout << "TAK\n"; set<int> secik; if(i-1 > 0) secik.insert(i-1); secik.insert(i); if(i+1 < n) secik.insert(i+1); int p = 1; while(sz(secik) < k-1){ secik.insert(p); p++; } for(auto u : secik) cout << u << " "; cout << "\n"; return; } cout << "NIE\n"; } void solve2(){ mnp[0] = INF; rep(i,1,n) mnp[i] = min(mnp[i-1],a[i]); mxs[n+1] = -INF; for(int i=n;i>=1;i--) mxs[i] = max(mxs[i+1],a[i]); rep(i,1,n-1) if(mnp[i] >= mxs[i+1]){ cout << "TAK\n"; cout << i << "\n"; return; } cout << "NIE\n"; } void solve3(){ mnp[0] = INF; rep(i,1,n) mnp[i] = min(mnp[i-1],a[i]); mxs[n+1] = -INF; for(int i=n;i>=1;i--) mxs[i] = max(mxs[i+1],a[i]); mnp[0] = -INF; mxs[n+1] = INF; rep(i,1,n) if(mnp[i-1] >= a[i] || a[i] >= mxs[i+1]){ cout << "TAK\n"; set<int> secik; if(i-1 > 0) secik.insert(i-1); if(i < n) secik.insert(i); int p = 1; while(sz(secik) < k-1){ secik.insert(p); p++; } for(auto u : secik) cout << u << " "; cout << "\n"; return; } cout << "NIE\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; rep(i,1,n) cin >> a[i]; if(k == 2) solve2(); else if(k == 3) solve3(); else solve(); }
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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define st first #define nd second #define pb push_back #define mp make_pair #define rep(i,a,b) for(ll i=(ll)a;i<=(ll)b;++i) #define all(a) a.begin(),a.end() #define sz(x) (int)(x).size() const int mxN = 5e5+7, INF = 1e9+7; int a[mxN], n, k; int mnp[mxN], mxs[mxN]; void solve(){ rep(i,1,n-1) if(a[i] >= a[i+1]){ cout << "TAK\n"; set<int> secik; if(i-1 > 0) secik.insert(i-1); secik.insert(i); if(i+1 < n) secik.insert(i+1); int p = 1; while(sz(secik) < k-1){ secik.insert(p); p++; } for(auto u : secik) cout << u << " "; cout << "\n"; return; } cout << "NIE\n"; } void solve2(){ mnp[0] = INF; rep(i,1,n) mnp[i] = min(mnp[i-1],a[i]); mxs[n+1] = -INF; for(int i=n;i>=1;i--) mxs[i] = max(mxs[i+1],a[i]); rep(i,1,n-1) if(mnp[i] >= mxs[i+1]){ cout << "TAK\n"; cout << i << "\n"; return; } cout << "NIE\n"; } void solve3(){ mnp[0] = INF; rep(i,1,n) mnp[i] = min(mnp[i-1],a[i]); mxs[n+1] = -INF; for(int i=n;i>=1;i--) mxs[i] = max(mxs[i+1],a[i]); mnp[0] = -INF; mxs[n+1] = INF; rep(i,1,n) if(mnp[i-1] >= a[i] || a[i] >= mxs[i+1]){ cout << "TAK\n"; set<int> secik; if(i-1 > 0) secik.insert(i-1); if(i < n) secik.insert(i); int p = 1; while(sz(secik) < k-1){ secik.insert(p); p++; } for(auto u : secik) cout << u << " "; cout << "\n"; return; } cout << "NIE\n"; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; rep(i,1,n) cin >> a[i]; if(k == 2) solve2(); else if(k == 3) solve3(); else solve(); } |