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

using namespace std;

typedef long long Zycie;

struct Potwor
{
    Zycie obr;
    Zycie bonus;
    int nr;
    Zycie bilans() const { return bonus - obr; }
};

struct PorPotwory
{
    bool operator()(const Potwor& p1, const Potwor& p2)
    {
        int bil1 = p1.bilans();
        int bil2 = p2.bilans();
        if (bil1 < 0 && bil2 < 0)       // wczesniej musi byc ten ktory
            return p1.bonus > p2.bonus;     // zwroci nam wiecej zycia
        else if (bil1 >= 0 && bil2 < 0)
            return true;
        else if (bil1 < 0 && bil2 >= 0)
            return false;
        else                            // w przypadku dodatniego bilansu najpierw
            return p1.obr < p2.obr;     // atakujemy tego co zadaje male obrazenia
    }
};

void wczytajDane(int n, vector<Potwor>& potwory)
{
    for (int i = 1; i <= n; ++i)
    {
        Potwor p;
        cin >> p.obr >> p.bonus;
        p.nr = i;
        potwory.push_back(p);
    }
}

bool sprawdz(Zycie z, const vector<Potwor>& potwory)
{
    Zycie bilans = z;
    for (vector<Potwor>::const_iterator it = potwory.begin(); it != potwory.end(); ++it)
    {
        bilans -= it->obr;
        if (bilans <= 0)
            return false;
        bilans += it->bonus;
    }
    return true;
}

void wypiszKolejnosc(const vector<Potwor>& potwory)
{
    for (vector<Potwor>::const_iterator it = potwory.begin(); it != potwory.end(); ++it)
        cout << it->nr << ' ';
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    Zycie z;
    cin >> n >> z;
    vector<Potwor> potwory;
    
    wczytajDane(n, potwory);
    sort(potwory.begin(), potwory.end(), PorPotwory());
    if (sprawdz(z, potwory))
    {
        cout << "TAK" << endl;
        wypiszKolejnosc(potwory);
    }
    else
    {
        cout << "NIE" << endl;
    }    
    
    return 0;
}