题解：CF2090C Dining Hall

BLuemoon_ · 2025-03-25 14:50:14 · 题解

link

思路

考虑最坏的情况，即每个人都要一个单独的桌子：

可以发现这是阶梯状分布的，于是我们用到的桌子最多 \sqrt{2n} 行 \sqrt{2n} 列的。

我们可以用一个 dis 函数计算每个格子距离原点的距离，注意每个桌子右上角的距离要 +2。使用两个 set 分别存下这些可能的被坐的桌子的每个点，一个 set 存所有能坐的位置，另一个存没被坐过的桌子。这样就可以根据不同的需求快速找答案了。

在有人坐进来时，删掉两个 set 中不能再被坐的点，注意判断这个点是否已经被删掉，否则会 RE。

代码

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using DB = double;

const int kMaxN = 5e4 + 5;

LL T = 1, n, a[kMaxN], ans;
string s;

void pr(bool pr) { cout << (pr ? "YES" : "NO") << '\n'; }
int dis(int x, int y) {
  if (x % 3 == 2 && y % 3 == 2) {
    return x + y + 2;
  } else {
    return x + y;
  }
}

struct P {
  int x, y;
  bool operator<(const P &o) const {
    return dis(x, y) != dis(o.x, o.y) ? dis(x, y) < dis(o.x, o.y) : (x != o.x ? x < o.x : y < o.y);
  }
};

set<P> f, g;

void del(int x, int y) {
  f.count({x, y}) && (f.erase({x, y}));
  x % 3 == 2 && (x--), y % 3 == 2 && (y--);
  g.count({x, y}) && (g.erase({x, y}));
  g.count({x, y + 1}) && (g.erase({x, y + 1}));
  g.count({x + 1, y}) && (g.erase({x + 1, y}));
  g.count({x + 1, y + 1}) && (g.erase({x + 1, y + 1}));
} 

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for (cin >> T; T; T--, ans = 0, f.clear(), g.clear()) {
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for (int i = 0; i * i <= n << 1; i++) {
      for (int j = 0; j * j <= n << 1; j++) {
        f.insert({3 * i + 1, 3 * j + 1}), f.insert({3 * i + 1, 3 * j + 2}), f.insert({3 * i + 2, 3 * j + 1}), f.insert({3 * i + 2, 3 * j + 2});
        g.insert({3 * i + 1, 3 * j + 1}), g.insert({3 * i + 1, 3 * j + 2}), g.insert({3 * i + 2, 3 * j + 1}), g.insert({3 * i + 2, 3 * j + 2});
      }
    }
    for (int i = 1; i <= n; i++) {
      if (a[i]) {
        cout << (*f.begin()).x << ' ' << (*f.begin()).y << '\n';
        del((*f.begin()).x, (*f.begin()).y);
      } else {
        cout << (*g.begin()).x << ' ' << (*g.begin()).y << '\n';
        del((*g.begin()).x, (*g.begin()).y);
      }
    }
  }
  return 0;
}