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
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct monster
{
   int id, dmg, restore, bilans, killed;

   monster(int id, int dmg, int restore) 
      : id(id), dmg(dmg), restore(restore), killed(false)
   {
      bilans = restore - dmg;
   }
};

bool dmg_cmp(const monster & m1, const monster & m2)
{
   return m1.dmg < m2.dmg;
}

bool dmg_rev_cmp(const monster* m1, const monster* m2)
{
   return m1->dmg >= m2->dmg;
}

bool bilans_rev_cmp(const monster & m1, const monster & m2)
{
   return m1.bilans >= m2.bilans;
}

int main(int argc, char const *argv[])
{
   ios_base::sync_with_stdio(false);
   long long z;
   int n;
   cin >> n >> z;
   vector<monster> positive;
   vector<monster> negative;

   for (int i = 1; i <= n ; ++i)
   {
      int dmg, restore;
      cin >> dmg >> restore;
      if (dmg <= restore)
         positive.push_back(monster(i, dmg, restore));
      else
         negative.push_back(monster(i, dmg, restore));
   }
   
   sort(positive.begin(), positive.end(), dmg_cmp);
   sort(negative.begin(), negative.end(), bilans_rev_cmp);
   
   vector<monster*> high_dmg;
   high_dmg.reserve(negative.size());
   for (vector<monster>::iterator m = negative.begin(); m != negative.end(); ++m)
   {
      high_dmg.push_back(&(*m));
   }

   sort(high_dmg.begin(), high_dmg.end(), dmg_rev_cmp);


   bool ok = true;
   for (vector<monster>::iterator m = positive.begin(); ok && m != positive.end(); ++m)
   {
      ok = m->dmg < z;
      z += m->bilans;
   }

   int to_kill = negative.size();
   vector<int> out_negative;
   out_negative.reserve(to_kill);
   vector<monster*>::iterator max_dmg_m = high_dmg.begin();
   vector<monster>::iterator  best_bilans_m = negative.begin();
   while(ok && to_kill > 0) {
      while ((*max_dmg_m)->killed) ++max_dmg_m;
      if ((*max_dmg_m)->dmg < z + best_bilans_m->bilans)
      {
         z += best_bilans_m->bilans;
         best_bilans_m->killed = true;
         out_negative.push_back(best_bilans_m->id);
         ++best_bilans_m;
      }
      else
      {
         z += (*max_dmg_m)->bilans;
         (*max_dmg_m)->killed = true;
         out_negative.push_back((*max_dmg_m)->id);
         ++max_dmg_m;
      }
      --to_kill;
      ok = z > 0;
   }

   if (ok)
   {
      cout << "TAK" << endl;
      for (vector<monster>::iterator m = positive.begin(); m != positive.end(); ++m)
         cout << m->id << " ";
      for (vector<int>::iterator mid = out_negative.begin(); mid != out_negative.end(); ++mid)
         cout << *mid << " ";
      cout << endl;
   }
   else
      cout << "NIE" << endl;

   return 0;
}