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

using namespace std;
typedef vector<unsigned int> pozycje;
typedef map<unsigned int, pozycje> koszt;
typedef map<int, koszt> zysk;

int main(void)
{
    ios_base::sync_with_stdio(0);
    zysk a;
    unsigned long long rows, life;
    cin >> rows >> life;
    unsigned int * ret = new unsigned int(rows);
    int k, b, z;
    long long calkowityZysk = life;
    for(unsigned int i = 1; i <= rows; ++i)
    {
        cin >> k >> b;
        z = b-k;
        a[z][k].push_back(i);
        calkowityZysk += z;
//        cout << b-k << " " << k << " " << i << endl;
    }
    if(calkowityZysk<=0)
    {
        cout << "NIE";
        return 0;
    }

    bool out = false;
    unsigned int i = 0;
    for(; i < rows; ++i)
    {
        if(out || a.rbegin()->first < 0)
            break;
        out = true;
//        cout << rows << " r c " << a.size() << endl;
        for(zysk::reverse_iterator itz = a.rbegin(); itz != a.rend(); itz++)
        {
            koszt::iterator itk = itz->second.begin();
            if(itk->first < life)
            {
                life += itz->first;
                ret[i] = *itk->second.rbegin();
//                cout << ret[i] << " itk " << itk->second.size()
//                        << " itz " << itz->second.size() << endl;
                itk->second.pop_back();
                if(itk->second.empty())
                {
//                    cout << "wywalilem itk " << itk->first << endl;
                    itz->second.erase(itk);
                    if(itz->second.empty())
                    {
//                        cout << "wywalilem itz " << itz->first << endl;
                        a.erase(itz->first);
                    }
                }
                out = false;
                break;
            }
        }
    }
    if(out == false && i < rows)
    {
        for(; i < rows; ++i)
        {
            if(out)
                break;
            out = true;
//            koszt::iterator maxKoszt = 0;
            for(zysk::iterator itz = a.begin(); itz != a.end(); itz++)
            {
                koszt::iterator itk = itz->second.begin();
                if(itk->first < life)
                {
                    life += itz->first;
                    ret[i] = *itk->second.rbegin();
                    itk->second.pop_back();
                    if(itk->second.empty())
                    {
                        itz->second.erase(itk);
                        if(itz->second.empty())
                        {
                            a.erase(itz->first);
                        }
                    }
                    out = false;
                    break;
                }
            }
        }
    }

    if(out)
        cout << "NIE" << endl;
    else
    {
        cout << "TAK" << endl << ret[0];
        for(int i = 1; i< rows; ++i)
            cout << " " << ret[i];
        cout << endl;
    }
    return 0;
}