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
#include <iostream>
#include <vector>
#include <algorithm>
//Potyczki Algorytmiczne 2014
//Zadanie: Bohater (BOH/B/2)
//Autor rozwiązania: Cwynar Damian

using namespace std;

class potwor{
public:
        int eliksir, atak, zysk, lp;
        bool zywy;
        bool operator < (const potwor& str) const{
        if (zysk<=0 || str.zysk<=0){
        return (eliksir > str.eliksir);
        }
        return (zysk > str.zysk);
}
};

bool porownaj_potwory(potwor a, potwor b){
return a.zysk<b.zysk;
}

int main()
{
    ios_base::sync_with_stdio(0); //wyłączenie synchrnizacji przyśpiesza strumienie

    int n; //liczba wrogów
    int zycie; //zycie bohatera

    cin >> n >> zycie;


    //tworzy tablicę potworów
    vector<potwor> potworki;
    vector<int> kolejnosc;
    potworki.resize(n);
    kolejnosc.resize(n);

    //wczyruje dane
    for(int i=0; i<n; i++){
    cin >> potworki[i].atak;
    cin >> potworki[i].eliksir;
    potworki[i].zysk=potworki[i].eliksir - potworki[i].atak;
    potworki[i].lp=i+1;
    potworki[i].zywy=true;
    }

    sort(potworki.begin(), potworki.end());

    int lp=0;
    for(int i=0; i<n;){
    if (zycie<=potworki[i].atak || !(potworki[i].zywy)) {
    i++;
    continue;
    } else if (zycie>potworki[i].atak){
    zycie-=potworki[i].atak;
    zycie+=potworki[i].eliksir;
    potworki[i].zywy=false;
    kolejnosc[lp]=potworki[i].lp;
    lp++;
    i=0;
    /*
    cout << "Zabiłem lp: " << potworki[i].lp << endl;
    cout << "HP teraz: " << zycie << endl;
    */
    }}

    bool wynik=true;

    for (int i=0; i<n; i++){
    if (potworki[i].zywy) wynik=false;
    }

    if (wynik){
    cout << "TAK\n";
    for (int i=0; i<n; i++){
    cout << kolejnosc[i] << " ";
    }
    } else {
    cout << "NIE";
    }

    return 0;
}