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 #include #include #include using namespace std; #define fir first.first #define sec first.second #define thi second #define N 100010 typedef pair, int> triple; int n, d, a, tree_size; unsigned long long z, fin; int res[N]; triple in[N]; vector P, M; int main() { scanf("%d%lld", &n, &z); fin = z; for (int i = 1; i <= n; i++) { scanf("%d%d", &d, &a); fin += d - a; if (d - a < 0) P.push_back(make_pair(make_pair(d, a), i)); else M.push_back(make_pair(make_pair(a, d), i)); } if (fin <= 0) { printf("NIE\n"); return 0; } sort(P.begin(), P.end()); // for (int i = 0; i < P.size(); i++) // { // printf("PLUS %d %d %d\n", P[i].fir, P[i].sec, P[i].thi); // } int j = 1; for (int i = 0; i < P.size(); i++, j++) { z -= P[i].fir; if (z <= 0) { printf("NIE\n"); return 0; } z += P[i].sec; res[j] = P[i].thi; } sort(M.begin(), M.end()); reverse(M.begin(), M.end()); // for (int i = 0; i < M.size(); i++) // { // printf("MINUS %d %d %d\n", M[i].fir, M[i].sec, M[i].thi); // } for (int i = 0; i < M.size(); i++, j++) { // printf("Z %d\n", z); z -= M[i].sec; if (z <= 0) { printf("NIE\n"); return 0; } z += M[i].fir; res[j] = M[i].thi; } printf("TAK\n"); for (int i = 1; i <= n; i++) printf("%d ", res[i]); printf("\n"); }