#include <algorithm> #include <functional> #include <iostream> #include <utility> #include <vector> template<class ForwardIt1, class ForwardIt2, class Comp> bool solve(ForwardIt1 a, ForwardIt1 aend, ForwardIt2 b, ForwardIt2 bend, Comp comp) { long long prev_at = 0; long long prev_av = 0; long long t = 0; for (; b != bend; ++b) { const auto& [bt, bv] = *b; long long v = 0; long long add = std::min(prev_av, bv); v += add; t += prev_at * add; prev_av -= add; for (; v < bv; ++a) { const auto& [at, av] = *a; prev_at = at; prev_av = av; long long add = std::min(av, bv - v); v += add; t += prev_at * add; prev_av -= add; } if (comp(bt * bv, t)) return false; t -= bt * bv; } return true; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--) { int n; std::cin >> n; std::vector<std::pair<int, long long>> ma, mb; for (int i = 0; i < n; i++) { int d, a, b; std::cin >> d >> a >> b; ma.emplace_back(a, d); mb.emplace_back(b, d); } std::sort(ma.begin(), ma.end()); std::sort(mb.begin(), mb.end()); std::cout << ( solve(ma.begin(), ma.end(), mb.begin(), mb.end(), std::less<> {}) && solve(ma.rbegin(), ma.rend(), mb.rbegin(), mb.rend(), std::greater<> {}) ? "TAK\n" : "NIE\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 | #include <algorithm> #include <functional> #include <iostream> #include <utility> #include <vector> template<class ForwardIt1, class ForwardIt2, class Comp> bool solve(ForwardIt1 a, ForwardIt1 aend, ForwardIt2 b, ForwardIt2 bend, Comp comp) { long long prev_at = 0; long long prev_av = 0; long long t = 0; for (; b != bend; ++b) { const auto& [bt, bv] = *b; long long v = 0; long long add = std::min(prev_av, bv); v += add; t += prev_at * add; prev_av -= add; for (; v < bv; ++a) { const auto& [at, av] = *a; prev_at = at; prev_av = av; long long add = std::min(av, bv - v); v += add; t += prev_at * add; prev_av -= add; } if (comp(bt * bv, t)) return false; t -= bt * bv; } return true; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--) { int n; std::cin >> n; std::vector<std::pair<int, long long>> ma, mb; for (int i = 0; i < n; i++) { int d, a, b; std::cin >> d >> a >> b; ma.emplace_back(a, d); mb.emplace_back(b, d); } std::sort(ma.begin(), ma.end()); std::sort(mb.begin(), mb.end()); std::cout << ( solve(ma.begin(), ma.end(), mb.begin(), mb.end(), std::less<> {}) && solve(ma.rbegin(), ma.rend(), mb.rbegin(), mb.rend(), std::greater<> {}) ? "TAK\n" : "NIE\n"); } return 0; } |