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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <iostream>
using namespace std;

int tplus[100000][3];
int tzero[100000][3];
int tminus[100000][3];
int tym[100000][3];

int usun(int tab[100000][3], int el)
{
	int j=0;
	for (int i=0; i<el; i++)
	{
		if (tab[i][2] != 0)
		{
			tab[j][0] = tab[i][0];
			tab[j][1] = tab[i][1];
			tab[j][2] = tab[i][2];
			j++;
		}
	}
	return j;
}

int partition(int tablica[100000][3], int p, int r) // dzielimy tablice na dwie czesci, w pierwszej wszystkie liczby sa mniejsze badz rowne x, w drugiej wieksze lub rowne od x
{
	int x = tablica[p][0]; // obieramy x
	int i = p, j = r, w; // i, j - indeksy w tabeli
	while (true) // petla nieskonczona - wychodzimy z niej tylko przez return j
	{
		while (tablica[j][0] > x) // dopoki elementy sa wieksze od x
			j--;
		while (tablica[i][0] < x) // dopoki elementy sa mniejsze od x
			i++;
		if (i < j) // zamieniamy miejscami gdy i < j
		{
			for(int k = 0; k < 3; k++)
			{
				w = tablica[i][k];
				tablica[i][k] = tablica[j][k];
				tablica[j][k] = w;
			}
			i++;
			j--;
		}
		else // gdy i >= j zwracamy j jako punkt podzialu tablicy
			return j;
	}
}
 
void quicksort(int tablica[100000][3], int p, int r) // sortowanie szybkie
{
	int q;
	if (p < r)
	{  
		q = partition(tablica,p,r); // dzielimy tablice na dwie czesci; q oznacza punkt podzialu
		quicksort(tablica, p, q); // wywolujemy rekurencyjnie quicksort dla pierwszej czesci tablicy
		quicksort(tablica, q+1, r); // wywolujemy rekurencyjnie quicksort dla drugiej czesci tablicy
	}
}

int main()
{
	ios_base::sync_with_stdio(0);

//Wczytywanie
	long long int hp; //zdrowie Bitora
	long long int khp; //końcowe zdrowie Bitora
	int pot; //ilość potworasków
	int miks; //ilość hp dawana przez miksturę
	int obr; //obrażenia zadawane przez potworaska
	cin>>pot;
	cin>>hp;
	
	khp = hp;
	
	for (int i=0; i<pot; i++)
	{
		cin>>obr;
		cin>>miks;
		if (miks - obr > 0)
		{
			tplus[i][0] = obr;
			tplus[i][1] = miks;
			tplus[i][2] = i+1;
		}
		else if (miks - obr < 0)
		{
			tminus[i][0] = miks;
			tminus[i][1] = obr;
			tminus[i][2] = i+1;
		}
		else
		{
			tzero[i][0] = obr;
			tzero[i][1] = miks;
			tzero[i][2] = i+1;
		}
		khp -= obr-miks; 
	}
	
	int pel=usun(tplus, pot); //ilość elementów tablicy tplus
	int zel=usun(tzero, pot);
	int mel=usun(tminus, pot);
	
	quicksort(tplus, 0, pel - 1);
	quicksort(tminus, 0, mel - 1);
	
//Sprawdzanie
	for (int i=0; i<pel; i++)
	{
		hp -= tplus[i][0];
		if (hp <= 0)
		{
			cout<<"NIE\n";
			return 0;
		}
		hp += tplus[i][1];
	}
	
	for (int i=0; i<zel; i++)
	{
		if (hp <= tzero[i][0])
		{
			cout<<"NIE\n";
			return 0;
		}
	}
	
	for (int i=0; i<mel; i++)
	{
		khp -= tminus[i][0];
		if (khp <= 0)
		{
			cout<<"NIE\n";
			return 0;
		}
		khp += tminus[i][1];
	}
	
//Wypisywanie
	if (hp != khp)
	{
		cout<<"NIE\n";
	}
	else
	{
		cout<<"TAK\n";
		for (int i=0; i<pel; i++)
			cout<< tplus[i][2]<<" ";
			
		for (int i=0; i<zel; i++)
			cout<< tzero[i][2]<<" ";
			
		for (int i=mel-1; i>=0; i-=1)
			cout<< tminus[i][2]<<" ";
	}
	return 0;
}