#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> // #define SHOWDEBUG const int MAX_N = 1000 * 1000; using lli = long long int; int volumes[MAX_N]; int source_temps[MAX_N]; int dest_temps[MAX_N]; struct cup_t { int volume; int temp; }; bool solve() { #ifdef SHOWDEBUG puts("--- BEGIN TEST ---"); #endif int n; scanf("%d", &n); std::vector<cup_t> source_cups; std::vector<cup_t> dest_cups; source_cups.reserve(n); dest_cups.reserve(n); while (n-- > 0) { int volume, source_temp, dest_temp; scanf("%d %d %d", &volume, &source_temp, &dest_temp); source_cups.push_back(cup_t{volume, source_temp}); dest_cups.push_back(cup_t{volume, dest_temp}); } auto cmp_cups = [](const cup_t& a, const cup_t& b) -> bool { return a.temp < b.temp; }; std::sort(source_cups.begin(), source_cups.end(), cmp_cups); std::sort(dest_cups.begin(), dest_cups.end(), cmp_cups); lli balance = 0; while (!dest_cups.empty()) { cup_t& sc = source_cups.back(); cup_t& dc = dest_cups.back(); const int t_diff = sc.temp - dc.temp; const int min_volume = std::min(sc.volume, dc.volume); balance += (lli)t_diff * (lli)min_volume; #ifdef SHOWDEBUG printf(" scup: %d %d\n", sc.temp, sc.volume); printf(" dcup: %d %d\n", dc.temp, dc.volume); printf(" balance: %lld\n", balance); #endif if (sc.volume < dc.volume) { source_cups.pop_back(); dc.volume -= min_volume; } else if (sc.volume > dc.volume) { dest_cups.pop_back(); sc.volume -= min_volume; } else { source_cups.pop_back(); dest_cups.pop_back(); } if (balance < 0) { return false; } } return (balance == 0); } int main() { int t; scanf("%d", &t); while (t-- > 0) { puts(solve() ? "TAK" : "NIE"); } 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 88 89 90 | #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> // #define SHOWDEBUG const int MAX_N = 1000 * 1000; using lli = long long int; int volumes[MAX_N]; int source_temps[MAX_N]; int dest_temps[MAX_N]; struct cup_t { int volume; int temp; }; bool solve() { #ifdef SHOWDEBUG puts("--- BEGIN TEST ---"); #endif int n; scanf("%d", &n); std::vector<cup_t> source_cups; std::vector<cup_t> dest_cups; source_cups.reserve(n); dest_cups.reserve(n); while (n-- > 0) { int volume, source_temp, dest_temp; scanf("%d %d %d", &volume, &source_temp, &dest_temp); source_cups.push_back(cup_t{volume, source_temp}); dest_cups.push_back(cup_t{volume, dest_temp}); } auto cmp_cups = [](const cup_t& a, const cup_t& b) -> bool { return a.temp < b.temp; }; std::sort(source_cups.begin(), source_cups.end(), cmp_cups); std::sort(dest_cups.begin(), dest_cups.end(), cmp_cups); lli balance = 0; while (!dest_cups.empty()) { cup_t& sc = source_cups.back(); cup_t& dc = dest_cups.back(); const int t_diff = sc.temp - dc.temp; const int min_volume = std::min(sc.volume, dc.volume); balance += (lli)t_diff * (lli)min_volume; #ifdef SHOWDEBUG printf(" scup: %d %d\n", sc.temp, sc.volume); printf(" dcup: %d %d\n", dc.temp, dc.volume); printf(" balance: %lld\n", balance); #endif if (sc.volume < dc.volume) { source_cups.pop_back(); dc.volume -= min_volume; } else if (sc.volume > dc.volume) { dest_cups.pop_back(); sc.volume -= min_volume; } else { source_cups.pop_back(); dest_cups.pop_back(); } if (balance < 0) { return false; } } return (balance == 0); } int main() { int t; scanf("%d", &t); while (t-- > 0) { puts(solve() ? "TAK" : "NIE"); } return 0; } |