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

//using namespace std;

struct smok
{
	int jad;
	int eli;
	int zysk;
	int nr;
};

int n,z,ws,ww,wyg[100001];

std::vector<struct smok> T;

typedef bool (*comp)(struct smok,struct smok);
bool cmpQ(struct smok S1,struct smok S2)			//jesli zysk<0, to najpierw walcz z silniejszym
{
	if (S1.zysk<0 && S2.zysk<0) return (S1.eli <= S2.eli); else	
	return (S1.zysk<=S2.zysk);
}

std::priority_queue<struct smok, std::vector<struct smok>, comp> PQ(cmpQ);

bool cmp (smok S1, smok S2) {return(S1.jad <= S2.jad);}
void wczytaj_sortuj(void)		//wczytuje dane i sortuje ROSNACO wzgledem kosztu pojedynku
{
	struct smok ss;
	int i,d,a;
	
	scanf("%d %d",&n,&z);
	for(i=1;i<=n;++i)
	{
		scanf("%d %d",&d,&a);
		ss.nr  = i;
		ss.jad = d;
		ss.eli = a;
		ss.zysk = a-d;
		T.push_back(ss);
	}

	std::sort(T.begin(), T.end(), cmp);

	ws = 0;
	ww = 0;
	return;
}


void dodaj_smoki_do_kolejki(int r)	//dodaje kolejne smoki o jadowitosci < r do kolejki PQ
{
	while(ws<n && T.at(ws).jad<r)
	{
		PQ.push(T.at(ws));
		ws++;		
	}
		
	return;
}

int walcz_ze_smokiem(void)
{
	struct smok S1;
	S1 = PQ.top();
		
	if (z>S1.jad) {z += S1.zysk; wyg[ww++] = S1.nr; PQ.pop();} else return 1;
	
	return 0;
}

int main()
{
	int i,f=0;
	
	wczytaj_sortuj();
	
	dodaj_smoki_do_kolejki(z);
	
	while(!PQ.empty() && f==0)
	{
		f = walcz_ze_smokiem();
		dodaj_smoki_do_kolejki(z);
	}
	
	if (ww<n) printf("NIE"); else {printf("TAK\n"); for(i=0;i<n;++i) printf("%d ",wyg[i]);}
	printf("\n");
	return 0;
}