记录编号	611353	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[THUPC 2025 Final] 食堂	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	121.057 s
提交时间	2026-01-28 13:26:10	内存使用	99.58 MiB

#include <bits/stdc++.h>
typedef std::tuple<int, int, int> tuple;
signed main () {
  freopen("thupc_2025_dining.in", "r", stdin);
  freopen("thupc_2025_dining.out", "w", stdout);
  std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
  int q; std::cin >> q; std::set<int> s0, s1[4], s2[4]; std::set<std::pair<int, int>> s; std::vector<int> w(q);
  auto id = [&] (int a, int b) {return (a + b) * (a + b + 1) / 2 + a;};
  auto get = [&] (int id) {int s = ceil((sqrt(9 + 8 * id) - 3) / 2), a = id - s * (s + 1) / 2; return std::make_pair(a, s - a);};
  auto add = [&] (int id, int u, int v, bool f = true) {
    if (!w[id]) s0.erase(id);
    for (int i = 0; i < 4; i++) if (!w[id] or w[id] == 1 << i) s1[i].erase(id);
    for (int i = 0; i < 4; i++) if (~w[id] >> i & 1) s2[i].erase(id);
    w[id] ^= 1 << (u << 1 | v);
    if (!w[id]) s0.insert(id);
    for (int i = 0; i < 4; i++) if (!w[id] or w[id] == 1 << i) s1[i].insert(id);
    for (int i = 0; i < 4; i++) if (~w[id] >> i & 1) s2[i].insert(id);
    if (f) {auto [a, b] = get(id); std::cout << 3 * a + u + 1 << ' ' << 3 * b + v + 1 << '\n';}
  };
  for (int i = 0; i < q; i++) {s0.insert(i); for (int j = 0; j < 4; j++) s1[j].insert(i), s2[j].insert(i);}
  for (int _ = 0; _ < q; _++) {
    int t; std::cin >> t;
    if (t == 1) {
      int o; std::cin >> o;
      if (o == 0) add(*s0.begin(), 0, 0);
      auto ask = [&] (const tuple &a) {
        auto [i, u, v] = a; auto [x, y] = get(i);
        return std::make_tuple(3 * (x + y) + 2 + u + v + u * v * 2, 3 * x + u, 3 * y + v);
      };
      auto checkmin = [&] (tuple &a, const tuple &b) {if (ask(a) > ask(b)) a = b;};
      if (o == 1) {
        tuple ans = std::make_tuple(q, 1, 1);
        for (int i = 0; i < 4; i++) checkmin(ans, std::make_tuple(*s1[3 - i].begin(), i >> 1, i & 1));
        auto [i, u, v] = ans; add(i, u, v);
      }
      if (o == 2) {
        tuple ans = std::make_tuple(q, 1, 1);
        for (int i = 0; i < 4; i++) checkmin(ans, std::make_tuple(*s2[i].begin(), i >> 1, i & 1));
        auto [i, u, v] = ans; add(i, u, v);
      }
    }
    if (t == 2) {
      int x, y; std::cin >> x >> y;
      int a = x / 3, b = y / 3, i = id(a, b);
      if (i >= q) {
        if (s.count(std::make_pair(x, y))) std::cout << "out\n", s.erase(std::make_pair(x, y));
        else std::cout << "in\n", s.insert(std::make_pair(x, y));
      }
      else {
        int u = x % 3 - 1, v = y % 3 - 1, p = u << 1 | v;
        std::cout << (w[i] >> p & 1 ? "out" : "in") << '\n'; add(i, u, v, false);
      }
    }
  }
  return 0;
}