#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; typedef vector<int> VI; typedef long long LL; typedef pair<int, int> PII; #define FOR(x, b, e) for (int x = b; x <= (e); ++x) #define FORD(x, b, e) for (int x = b; x >= (e); --x) #define REP(x, n) for (int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int) (x).size()) #define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second #define MP make_pair #define INF 1000000001 int sign(int k) { if (k > 0) return 1; if (k < 0) return -1; return 0; } struct Monster { int d, a, n, da, s; Monster(int _d = 0, int _a = 0, int _n = 0) : d(_d), a(_a), n(_n) { da = a - d; s = sign(da); } bool operator< (const Monster& m) const { if (s != m.s) return da > m.da; if (da >= 0) { if (d != m.d) return d < m.d; else return a > m.a; } else { // da < 0 if (a != m.a) return a > m.a; else return d > m.d; } } }; bool CanWin(const vector<Monster>& m, LL z) { for (auto& x: m) { if (z <= x.d) return false; z += x.da; } return z > 0; } int main() { int n, d, a; LL z; vector<Monster> M; scanf("%d %lld\n", &n, &z); FOR(i, 1, n) { scanf("%d %d\n", &d, &a); M.PB(Monster(d, a, i)); } sort(ALL(M)); bool res = CanWin(M, z); printf(res ? "TAK\n" : "NIE\n"); if (res) REP(i, n) { printf("%d", M[i].n); putchar(i == n - 1 ? '\n' : ' '); } return 0; }
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 <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; typedef vector<int> VI; typedef long long LL; typedef pair<int, int> PII; #define FOR(x, b, e) for (int x = b; x <= (e); ++x) #define FORD(x, b, e) for (int x = b; x >= (e); --x) #define REP(x, n) for (int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int) (x).size()) #define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second #define MP make_pair #define INF 1000000001 int sign(int k) { if (k > 0) return 1; if (k < 0) return -1; return 0; } struct Monster { int d, a, n, da, s; Monster(int _d = 0, int _a = 0, int _n = 0) : d(_d), a(_a), n(_n) { da = a - d; s = sign(da); } bool operator< (const Monster& m) const { if (s != m.s) return da > m.da; if (da >= 0) { if (d != m.d) return d < m.d; else return a > m.a; } else { // da < 0 if (a != m.a) return a > m.a; else return d > m.d; } } }; bool CanWin(const vector<Monster>& m, LL z) { for (auto& x: m) { if (z <= x.d) return false; z += x.da; } return z > 0; } int main() { int n, d, a; LL z; vector<Monster> M; scanf("%d %lld\n", &n, &z); FOR(i, 1, n) { scanf("%d %d\n", &d, &a); M.PB(Monster(d, a, i)); } sort(ALL(M)); bool res = CanWin(M, z); printf(res ? "TAK\n" : "NIE\n"); if (res) REP(i, n) { printf("%d", M[i].n); putchar(i == n - 1 ? '\n' : ' '); } return 0; } |