#include<bits/stdc++.h> using namespace std; int tab[1000005]; bool odw[1000005]; int a,k; void solve2() { vector<int> prefmin(a+2, 0), prefmax(a+2, 0), sufmin(a+2, 0), sufmax(a+2, 0); prefmin[1] = tab[1]; prefmax[1] = tab[1]; sufmax[a] = tab[a]; sufmin[a] = tab[a]; for(int x=2;x<=a;x++) { prefmin[x] = min(prefmin[x-1], tab[x]); prefmax[x] = max(prefmax[x-1], tab[x]); } for(int x=a-1;x>=1;x--) { sufmin[x] = min(sufmin[x+1], tab[x]); sufmax[x] = max(sufmax[x+1], tab[x]); } for(int x=1;x<a;x++) { if(prefmin[x] >= sufmax[x+1]) { cout<<"TAK\n"; cout<<x<<'\n'; exit(0); } } cout<<"NIE\n"; } void solve3() { int mini = 1e9+7, maks = 0; for(int x=1;x<=a;x++) { mini = min(mini, tab[x]); maks = max(maks, tab[x]); } for(int x=1;x<a;x++) if(tab[x] == maks) { cout<<"TAK\n"; if(x == 1) cout<<1<<" "<<2<<'\n'; else cout<<x-1<<" "<<x<<'\n'; exit(0); } for(int x=2;x<=a;x++) if(tab[x] == mini) { cout<<"TAK\n"; if(x == a) cout<<a-2<<" "<<a-1<<'\n'; else cout<<x-1<<" "<<x<<'\n'; exit(0); } cout<<"NIE\n"; } void solve4() { for(int x=1;x<a;x++) { if(tab[x] >= tab[x+1]) { cout<<"TAK"<<'\n'; vector<int> res; if(x == 1) { odw[1] = true; odw[2] = true; odw[3] = true; res = {1, 2, 3}; } else { odw[x - 1] = true; odw[x] = true; res = {x - 1, x}; if(x + 1 != a) { odw[x + 1] = true; res.push_back(x+1); } } for(int y=1;res.size() != k - 1; y++) if(!odw[y]) { odw[y] = true; res.push_back(y); } sort(res.begin(), res.end()); for(auto y : res) cout<<y<<" "; cout<<'\n'; exit(0); } } cout<<"NIE\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>a>>k; for(int x=1;x<=a;x++) cin>>tab[x]; if(k == 2) solve2(); else if(k == 3) solve3(); else solve4(); 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 | #include<bits/stdc++.h> using namespace std; int tab[1000005]; bool odw[1000005]; int a,k; void solve2() { vector<int> prefmin(a+2, 0), prefmax(a+2, 0), sufmin(a+2, 0), sufmax(a+2, 0); prefmin[1] = tab[1]; prefmax[1] = tab[1]; sufmax[a] = tab[a]; sufmin[a] = tab[a]; for(int x=2;x<=a;x++) { prefmin[x] = min(prefmin[x-1], tab[x]); prefmax[x] = max(prefmax[x-1], tab[x]); } for(int x=a-1;x>=1;x--) { sufmin[x] = min(sufmin[x+1], tab[x]); sufmax[x] = max(sufmax[x+1], tab[x]); } for(int x=1;x<a;x++) { if(prefmin[x] >= sufmax[x+1]) { cout<<"TAK\n"; cout<<x<<'\n'; exit(0); } } cout<<"NIE\n"; } void solve3() { int mini = 1e9+7, maks = 0; for(int x=1;x<=a;x++) { mini = min(mini, tab[x]); maks = max(maks, tab[x]); } for(int x=1;x<a;x++) if(tab[x] == maks) { cout<<"TAK\n"; if(x == 1) cout<<1<<" "<<2<<'\n'; else cout<<x-1<<" "<<x<<'\n'; exit(0); } for(int x=2;x<=a;x++) if(tab[x] == mini) { cout<<"TAK\n"; if(x == a) cout<<a-2<<" "<<a-1<<'\n'; else cout<<x-1<<" "<<x<<'\n'; exit(0); } cout<<"NIE\n"; } void solve4() { for(int x=1;x<a;x++) { if(tab[x] >= tab[x+1]) { cout<<"TAK"<<'\n'; vector<int> res; if(x == 1) { odw[1] = true; odw[2] = true; odw[3] = true; res = {1, 2, 3}; } else { odw[x - 1] = true; odw[x] = true; res = {x - 1, x}; if(x + 1 != a) { odw[x + 1] = true; res.push_back(x+1); } } for(int y=1;res.size() != k - 1; y++) if(!odw[y]) { odw[y] = true; res.push_back(y); } sort(res.begin(), res.end()); for(auto y : res) cout<<y<<" "; cout<<'\n'; exit(0); } } cout<<"NIE\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>a>>k; for(int x=1;x<=a;x++) cin>>tab[x]; if(k == 2) solve2(); else if(k == 3) solve3(); else solve4(); return 0; } |