#include "cstdio" #include "algorithm" using namespace std; long long n,k,a,b,p,m,z,wyn[100005],w; pair <pair<long long,long long>, pair<long long,long long> > plusy[100005],zera[100005],minusy[100005]; bool ok; int main() { scanf ("%lld%lld", &n, &k); for (int i=0; i<n; i++) { scanf ("%lld%lld", &a, &b); if (a<b) { plusy[p].first.first=a; plusy[p].first.second=(b-a)*(-1); plusy[p].second.first=b; plusy[p].second.second=i+1; p++; } else if (a>b) { minusy[m].first.first=b*(-1); minusy[m].second.first=a; minusy[m].second.second=i+1; m++; } else { zera[z].first.first=a; zera[z].first.second=(b-a)*(-1); zera[z].second.first=b; zera[z].second.second=i+1; z++; } } sort (plusy, plusy+p); sort (zera, zera+z); sort (minusy, minusy+m); ok=true; for (int i=0; i<p; i++) { k-=plusy[i].first.first; if (k<=0) { ok=false; break; } k+=plusy[i].second.first; wyn[w]=plusy[i].second.second; w++; } if (k>0) { for (int i=0; i<z; i++) { k-=zera[i].first.first; if (k<=0) { ok=false; break; } k+=zera[i].second.first; wyn[w]=zera[i].second.second; w++; } } if (k>0) { for (int i=0; i<m; i++) { k-=minusy[i].second.first; if (k<=0) { ok=false; break; } k+=(minusy[i].first.first*(-1)); wyn[w]=minusy[i].second.second; w++; } } if (!ok) printf ("NIE\n"); else { printf ("TAK\n"); for (int i=0; i<w; i++) printf ("%lld ", wyn[i]); } 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 | #include "cstdio" #include "algorithm" using namespace std; long long n,k,a,b,p,m,z,wyn[100005],w; pair <pair<long long,long long>, pair<long long,long long> > plusy[100005],zera[100005],minusy[100005]; bool ok; int main() { scanf ("%lld%lld", &n, &k); for (int i=0; i<n; i++) { scanf ("%lld%lld", &a, &b); if (a<b) { plusy[p].first.first=a; plusy[p].first.second=(b-a)*(-1); plusy[p].second.first=b; plusy[p].second.second=i+1; p++; } else if (a>b) { minusy[m].first.first=b*(-1); minusy[m].second.first=a; minusy[m].second.second=i+1; m++; } else { zera[z].first.first=a; zera[z].first.second=(b-a)*(-1); zera[z].second.first=b; zera[z].second.second=i+1; z++; } } sort (plusy, plusy+p); sort (zera, zera+z); sort (minusy, minusy+m); ok=true; for (int i=0; i<p; i++) { k-=plusy[i].first.first; if (k<=0) { ok=false; break; } k+=plusy[i].second.first; wyn[w]=plusy[i].second.second; w++; } if (k>0) { for (int i=0; i<z; i++) { k-=zera[i].first.first; if (k<=0) { ok=false; break; } k+=zera[i].second.first; wyn[w]=zera[i].second.second; w++; } } if (k>0) { for (int i=0; i<m; i++) { k-=minusy[i].second.first; if (k<=0) { ok=false; break; } k+=(minusy[i].first.first*(-1)); wyn[w]=minusy[i].second.second; w++; } } if (!ok) printf ("NIE\n"); else { printf ("TAK\n"); for (int i=0; i<w; i++) printf ("%lld ", wyn[i]); } return 0; } |