1 条题解

  • 0
    @ 2026-5-5 1:37:47
    #include <bits/stdc++.h>
    using ll = long long;
    
    int b, k, w;
    
    int dist(std::pair<int, int> p1, std::pair<int, int> p2) {
      return std::abs(p1.first - p2.first) + std::abs(p1.second - p2.second);
    }
    auto query(std::vector<std::pair<int, int>> ve) {
      std::cout << "? ";
      for (auto [a, b] : ve) std::cout << a << " " << b << " ";
      std::cout << std::endl, std::cerr << std::endl;
      std::vector<int> ret(k * ve.size());
      for (auto &x : ret) std::cin >> x;
      return ret;
    }
    
    std::mt19937 rnd;
    int rdi(int l, int r) { return std::uniform_int_distribution<int>(l, r)(rnd); }
    
    int main() {
      std::cin.tie(0)->sync_with_stdio(0);
      std::cin >> b >> k >> w;
      auto q1 = query({{-b, -b}, {-b, b}});
      std::vector<std::pair<int, int>> a;
      for (int i = 0; i < (int)q1.size(); i++)
        for (int j = 0; j < (int)q1.size(); j++) {
          int v1 = q1[i], v2 = q1[j];
          int x = (-4 * b + v1 + v2) / 2;
          int y = (v1 - v2) / 2;
          if (x + y + 2 * b == v1 && x - y + 2 * b == v2 && x >= -b && x <= b &&
              y >= -b && y <= b)
            a.emplace_back(x, y);
        }
      std::sort(a.begin(), a.end());
      a.erase(std::unique(a.begin(), a.end()), a.end());
    
      std::vector<int> d(a.size());
      std::vector<std::pair<int, int>> pa;
      std::set<int> s;
      for (int i = (int)a.size() - 1; i >= 0; i--) {
        auto [x, y] = a[i];
        int ok = 0;
        auto chk = [&](int px, int py) {
          int di = dist({px, py}, {x, y});
          if (s.count(di)) return false;
          std::set<int> tmp;
          tmp.insert(di);
          for (int j = i + 1; j < (int)a.size(); j++)
            if (tmp.count(dist(a[j], {px, py})))
              return false;
            else
              tmp.insert(d[j]);
          return true;
        };
        for (auto [px, py] : pa)
          if (chk(px, py)) {
            ok = 1;
            d[i] = dist({px, py}, {x, y});
            break;
          }
        if (!ok) {
          int px = rdi(-1e8, 1e8), py = y;
          while (!chk(px, py)) px = rdi(-1e8, 1e8), py = y;
          d[i] = dist({px, py}, {x, y});
          pa.emplace_back(px, py);
          for (int j = i; j < (int)a.size(); j++) s.insert(dist(a[j], pa.back()));
        }
        for (auto [px, py] : pa) s.insert(dist({px, py}, {x, y}));
      }
      auto q2 = query(pa);
      std::vector<std::pair<int, int>> ans;
      for (int i = 0; i < (int)a.size(); i++) {
        if (std::count(q2.begin(), q2.end(), d[i])) {
          ans.push_back(a[i]);
          for (auto [px, py] : pa)
            q2.erase(std::find(q2.begin(), q2.end(), dist({px, py}, a[i])));
        }
      }
    
      std::cout << "! ";
      for (auto [x, y] : ans) std::cout << x << " " << y << " ";
      std::cout << std::endl;
    }
    
    • 1

    信息

    ID
    7352
    时间
    2000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者