#include <bits/stdc++.h> using namespace std; int T[500100]; int Mi[500100]; int Ma[500100]; int St[500100]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; int mi=INT_MAX; for(int i=0;i<n;i++){ cin>>T[i]; mi = min(mi,T[i]); Mi[i]=mi; } int ma = -1; for(int i=n-1;i>=0;i--){ ma=max(ma,T[i]); Ma[i]=ma; } if(k==2){ for(int i=1;i<n;i++){ if(Mi[i-1]>=Ma[i]){ cout<<"TAK"<<"\n"<<i<<"\n"; return 0; } } cout<<"NIE"<<"\n"; return 0; } if(k==3){ if(T[0]>=T[1]){ cout<<"TAK"<<"\n"; cout<<1<<" "<<2<<"\n"; return 0; } if(T[n-1]<=T[n-2]){ cout<<"TAK"<<"\n"; cout<<n-1<<" "<<n<<"\n"; return 0; } ma=-1; mi=INT_MAX; int poz2=0; int poz =0; for(int i=0;i<n;i++){ if(T[i]>ma){ ma=T[i]; poz=i; } if(T[i]<=mi){ mi=T[i]; poz2=i; } } if(poz==n-1 and poz2==0){ cout<<"NIE"<<"\n"; return 0; } cout<<"TAK"<<"\n"; if(poz2==0){ cout<<poz<<" "<<poz+1<<"\n"; } else{ cout<<poz2<<" "<<poz2+1<<"\n"; } return 0; } if(k>=4){ k--; int pop=T[0]; for(int i=1;i<n;i++){ if(T[i]<=pop){ cout<<"TAK"<<"\n"; St[i+1]=1; k--; St[i]=1; k--; if(i!=1){ St[i-1]=1; k--; } for(int j=0;j<n;j++){ if(k>0 and St[j]!=1){ St[j]=1; k--; } if(St[j]==1){ cout<<j+1<<" "; } } cout<<"\n"; return 0; } pop=T[i]; } cout<<"NIE"<<"\n"; 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 | #include <bits/stdc++.h> using namespace std; int T[500100]; int Mi[500100]; int Ma[500100]; int St[500100]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k; cin>>n>>k; int mi=INT_MAX; for(int i=0;i<n;i++){ cin>>T[i]; mi = min(mi,T[i]); Mi[i]=mi; } int ma = -1; for(int i=n-1;i>=0;i--){ ma=max(ma,T[i]); Ma[i]=ma; } if(k==2){ for(int i=1;i<n;i++){ if(Mi[i-1]>=Ma[i]){ cout<<"TAK"<<"\n"<<i<<"\n"; return 0; } } cout<<"NIE"<<"\n"; return 0; } if(k==3){ if(T[0]>=T[1]){ cout<<"TAK"<<"\n"; cout<<1<<" "<<2<<"\n"; return 0; } if(T[n-1]<=T[n-2]){ cout<<"TAK"<<"\n"; cout<<n-1<<" "<<n<<"\n"; return 0; } ma=-1; mi=INT_MAX; int poz2=0; int poz =0; for(int i=0;i<n;i++){ if(T[i]>ma){ ma=T[i]; poz=i; } if(T[i]<=mi){ mi=T[i]; poz2=i; } } if(poz==n-1 and poz2==0){ cout<<"NIE"<<"\n"; return 0; } cout<<"TAK"<<"\n"; if(poz2==0){ cout<<poz<<" "<<poz+1<<"\n"; } else{ cout<<poz2<<" "<<poz2+1<<"\n"; } return 0; } if(k>=4){ k--; int pop=T[0]; for(int i=1;i<n;i++){ if(T[i]<=pop){ cout<<"TAK"<<"\n"; St[i+1]=1; k--; St[i]=1; k--; if(i!=1){ St[i-1]=1; k--; } for(int j=0;j<n;j++){ if(k>0 and St[j]!=1){ St[j]=1; k--; } if(St[j]==1){ cout<<j+1<<" "; } } cout<<"\n"; return 0; } pop=T[i]; } cout<<"NIE"<<"\n"; return 0; } } |