#P9080. 「HNOI2021 省集 Day2」AK 啦!

    ID: 5162 交互题 5000ms 512MiB 尝试: 91 已通过: 11 难度: 7 上传者: 标签>难度分类提高+/省选-离线与分治分治算法交互与信息策略自适应查询校验查询CF2300杂项交互题

「HNOI2021 省集 Day2」AK 啦!

这是一道交互题。

题目描述

二维平面上有 n+mn+m 条直线 (n(n 条平行于 x,mx, m 条平行于 y)y), 你可以询问点 (x,y)(x, y), 以得到距离 (x,y)(x, y) 最近的直线 (的距离 )), 所有直线到原点距离小于 10810^{8} 。

你需要找到这 n+mn+m 条直线。同方向的直线坐标互不相同。

你需要实现函数 std::pair<std::vector<int>,std::vector<int> > solve();, 其中 pair 的 first 存的是所有平行于 xx 轴的直线, second 则是平行于 yy 的直线。

你可以调用 int query(int x,int y);, 其中 ∣x∣,∣y∣≤108|x|,|y| \leq 10^{8}, 返回的是到最近的直线距离。

使用 C++17 或以上版本。请在提交源码开头包含 grader.cpp,并实现 solve 函数。平行于 xx 轴的直线用其 yy 坐标表示,另一组用 xx 坐标表示。

你需要在 2×1052\times 10^5 次内找出这些线, 这些线是在开始是确定的,不会随你的询问而改变。

数据范围

本题采用 Subtask。

Subtask 编号 特殊限制 分值
11 n,m≤10n,m\le 10 1010
22 n,m≤100n,m\le 100
33 n≤10n\le 10 2020
44 n,m≤10000n,m\le 10000 6060