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
#include <cstdio>
#include <algorithm>

const int N = 105;
int n, m, mm, L[N], R[N], D[N], E[N];
int n1, n2, h1, h2, q1[N], q2[N];
int n3, q3[N];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d%d", &L[i], &R[i], &D[i]);
    if (R[i] > mm) mm = R[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (L[j] >= L[i]) continue;
      std::swap(L[i], L[j]);
      std::swap(R[i], R[j]);
      std::swap(D[i], D[j]);
    }
  }

  for (int i = 1; i <= n; ++i) q1[++n1] = i;
  h1 = 1;
  for (int i = 0; i <= mm; ++i) {
    n3 = 0; h2 = 1;
    for (int j = 1; j <= m; ++j) {
      int u1 = (h1 <= n1) ? L[q1[h1]] : -1;
      int u2 = (h2 <= n2) ? R[q2[h2]] : -1;
      if (!~u1 && !~u2) break;
      if (!~u2 || (~u1 && u1 < u2)) {
        if (u1 < i) {
          puts("NIE");
          return 0;
        }
        ++E[q1[h1]]; q3[++n3] = q1[h1];
        ++h1;
      } else {
        if (u2 < i) {
          puts("NIE");
          return 0;
        }
        ++E[q2[h2]]; ++h2;
      }
    }
    for (int j = 1; j <= n2; ++j) {
      if (E[q2[j]] == D[q2[j]]) {
        for (int k = j; k < n2; ++k)
          q2[k] = q2[k + 1];
        --n2, --j;
      }
    }
    for (int j = 1; j <= n3; ++j) {
      if (D[q3[j]] == 1) continue;
      q2[++n2] = q3[j];
      for (int k = n2; k > 1; --k)
        if (R[q2[k]] < R[q2[k - 1]])
          std::swap(q2[k], q2[k - 1]);
    }
  }
  if (h1 <= n1 || n2 != 0) puts("NIE");
  else puts("TAK");
  return 0;
}