1 条题解
-
0
#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
- 上传者