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
121
122
123
124
125
126
127
128
/* Author: Dominik Wójt */
/* Problem: Bohater, Potyczki Algorytmiczne 2014 */

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

#define MY_ASSERT(condition) \
    do \
    { \
        if(!(condition)) \
        { \
            std::cerr << "assert failed: " << #condition << std::endl; \
            std::abort(); \
        } \
    } \
    while(false)
//------------------------------------------------------------------------------
typedef long int lint;
typedef long int llint;
//------------------------------------------------------------------------------
template<typename T>
T checked_read(const T min, const T max)
{
    T n;
    std::cin >> n;
    MY_ASSERT(std::cin);
    MY_ASSERT(min<=n && n<=max);
    return n;
}
//------------------------------------------------------------------------------
struct Monster
{
    lint cost;
    lint reward;
    lint index;
};
//------------------------------------------------------------------------------
lint gain(Monster monster)
{
    return monster.reward - monster.cost;
}
//------------------------------------------------------------------------------
lint less_by_cost(Monster a, Monster b)
{
    return a.cost < b.cost;
}
//------------------------------------------------------------------------------
lint greater_by_reward(Monster a, Monster b)
{
    return a.reward > b.reward;
}
//------------------------------------------------------------------------------
void make_optimal_order(std::vector<Monster> &monsters)
{
    typedef std::vector<Monster>::iterator iterator;
    iterator left = monsters.begin();
    iterator right = monsters.end()-1;
    while(left<right)
    {
        while(left<right && gain(*left)>=0)
            left++;
        while(left<right && gain(*right)<0)
            right--;
        while(left<right && gain(*left)<0 && gain(*right)>=0)
        {
            std::swap(*left,*right);
            left++;
            right--;
        }
    }
    if(gain(*left)>=0)
        left++;
    MY_ASSERT(left>=monsters.end() || gain(*left)<0);
    MY_ASSERT(left-1<monsters.begin() || gain(*(left-1))>=0);
    //at this point everything in range begin to left should have gain>=0

    std::sort(monsters.begin(), left, less_by_cost);
    std::sort(left, monsters.end(), greater_by_reward);
}
//------------------------------------------------------------------------------
bool check_game_success( const lint start_health,
    const std::vector<Monster> &monsters)
{
    llint health = start_health;
    typedef std::vector<Monster>::const_iterator iterator;
    for(iterator monster=monsters.begin(); monster<monsters.end(); ++monster)
    {
        if(monster->cost >= health)
            return false;
        health += gain(*monster);
    }
    return true;
}
//------------------------------------------------------------------------------
int main()
{
    const lint n = checked_read<lint>( 1, 100000 );
    const lint z = checked_read<lint>( 1, 100000 );

    std::vector<Monster> monsters( n );

    for(int i=0; i<n; i++)
    {
        monsters[i].cost = checked_read<lint>( 0, 100000 );
        monsters[i].reward = checked_read<lint>( 0, 100000 );
        monsters[i].index = i;
    }

    make_optimal_order(monsters);

    if(check_game_success(z, monsters))
    {
        std::cout << "TAK\n";
        for(int i=0; i<n-1; i++)
        {
            std::cout << monsters[i].index+1 << " ";
        }
        std::cout << monsters.back().index+1 << "\n";
    }
    else
    {
        std::cout << "NIE\n";
    }

    return 0;
}