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
#include <cstdio>
#include <stack>

const unsigned int zmax=100000;
const unsigned int nmax=100000;

struct monster {
       unsigned int monsterid;
       unsigned int monsterpower;
       unsigned int healthpack;
       int lifegain;
       bool type;
};

void quicksort(monster*,int,int);
unsigned int divide(monster*,int,int);

int main() {
    unsigned int z,n,pwr,hp;
    long long int life;
    std::stack <unsigned int> st1,st2;
    monster monsters[nmax];
    scanf("%d",&n);
    scanf("%d",&z);
    life = z;
    for(int i=0; i<n; i++) {
            scanf("%u %u",&pwr,&hp);
            monsters[i].monsterid=i+1;
            monsters[i].monsterpower=pwr;
            monsters[i].healthpack=hp;
            monsters[i].lifegain=hp-pwr;
            if (monsters[i].lifegain>=0) monsters[i].type=true;
            else monsters[i].type=false;
    }
    
    bool ispossible=true;
    quicksort(monsters,0,n-1);
    
   /* for(int i=0; i<n; i++) {
            printf("Monster id: %u, monster power: %u, health pack: %u, life gain: %d\n",monsters[i].monsterid,monsters[i].monsterpower,monsters[i].healthpack,monsters[i].lifegain);
    }*/
    
    for(int i=0; i<n; i++) if(monsters[i].type) {
            if(life>monsters[i].monsterpower) {
                         life+=monsters[i].lifegain; 
                         st1.push(monsters[i].monsterid);                
            } else {
                   ispossible=false;
                   break;
            }
    }
    
    if(ispossible) for(int i=n-1; i>=0; i--) if(!monsters[i].type) {
            if(life>monsters[i].monsterpower) {
                         life+=monsters[i].lifegain; 
                         st1.push(monsters[i].monsterid);                
            } else {
                   ispossible=false;
                   break;
            }
    }
    
    if (ispossible) {
       printf("TAK\n");
       while(!st1.empty()) {
                           st2.push(st1.top());
                           st1.pop();
       }
       while(!st2.empty()) {
                           printf("%u ",st2.top());
                           st2.pop();
       }
    } else {
           printf("NIE");
    }
    return 0;
}

void quicksort(monster* tab, int s, int e) {
     if (s<e) {
        unsigned int p = divide(tab,s,e);
        quicksort(tab,s,p-1);
        quicksort(tab,p+1,e);         
     }
}

unsigned int divide(monster* tab, int s, int e) {
         monster temp;
         int i,j;
         i=s;
         j=e-1;
         while(i<j) {
                    while((tab[i].monsterpower<=tab[e].monsterpower)&&(i<j)) i++;
                    while((tab[j].monsterpower>tab[e].monsterpower)&&(i<j)) j--;
                    temp=tab[i];
                    tab[i]=tab[j];
                    tab[j]=temp;
         }
         temp=tab[j];
         tab[j]=tab[e];
         tab[e]=temp;         
         return j;
}