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;
}