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
#include <stdio.h>

struct struktura{
int *wsp;
int *lp;
}minion;

void swap(int* a, int* b)
{
 int temp = *a;
 *a = *b;
 *b = temp;
}

void quicksort( int tab[], int tab2[], int left, int right )
{
    int i = left;
    int j = right;
    int x = tab[( left + right ) / 2 ];
    do
    {
        while( tab[ i ] < x )
             i++;

        while( tab[ j ] > x )
             j--;

        if( i <= j )
        {
            swap( &tab[ i ], &tab[ j ] );
            swap( &tab2[ i ], &tab2[ j ] );

            i++;
            j--;
        }
    } while( i <= j );

    if( left < j ) quicksort( tab, tab2, left, j );

    if( right > i ) quicksort( tab, tab2, i, right );

}

int main()
{
    int *wsp;
    int atk, heal;
    int n, z, t, i;

    do scanf("%d %d", &n, &z);
        while( (n < 1) || (n > 100000) || (z < 1) || (z > 100000) );

    minion.wsp = (int*) malloc(n * sizeof *minion.wsp);
    minion.lp = (int*) malloc(n * sizeof *minion.lp);

    for(i = 0 ; i < n ; i++)
    {
        do scanf("%d %d", &atk, &heal);
        while( (atk < 0) || (atk > 100000) || (heal < 0) || (heal > 100000) );
        minion.lp[i] = i + 1;
        minion.wsp[i] = heal - atk;
    }

    quicksort(minion.wsp, minion.lp, 0, n);

    i = 0;
    do
    {
        z += minion.wsp[n-i-1];
        i++;
    } while(i != n);

    if(z > 0)
    {
        printf("TAK\n");

        i = 0;
        do
        {
            printf("%d ", minion.lp[n-i-1]);
            i++;
        }while(i != n);
    } else printf("NIE");

    free (minion.wsp);
    free (minion.lp);

    return 0;
}