#PQJ1876x9908. QOJ 1876_9908
QOJ 1876_9908
第一试平原(plain) IOI2025 中国国家集训队集中培训 平原(plain) 【题目背景】 “只要你心里的念是真的,只要你心里的念是诚的,高山大海都会给你让路。”—— 《平原上的摩西》 【题目描述】 .这.是.一.道.交.互.题。 在二维平面上有一条.未.知的、不与y 轴平行的直线L。设L(x0) 表示直线L 与 x = x0 的交点纵坐标。 给定值域V ,L 额外满足以下性质: • 对于任意整数0 ≤x, y ≤V ,L(x)̸ = y; • 0 ≤L(0), L(V ) ≤V 。 此时L 将S = {0, 1, 2, · · · , V } × {0, 1, 2, · · · , V } 分割成两个点集SL = {(x, y) ∈S | L(x) > y} 和SL = {(x, y) ∈S | L(x) < y},且它们都不是空集。 你可以向交互库询问至多limit 次询问。每次询问给出整数0 ≤x, y ≤V ,你可以 得到(x, y) 属于SL 还是SL。 你需要找到直线L′,其不经过S 中任何一个点,且L′ 和L 将S 划分为同样的两 个点集。形式化地,L′ 需要满足∀(x, y) ∈SL, L′(x) > y 且∀(x, y) ∈SL, L′(x) < y。 【实现细节】 请确保你的程序开头有#include "plain.h"。 你不需要也不应该实现主函数。你需要实现以下函数: • std::tuple<long long, int, long long, int> Find(int task_id, int V, int limit); – 其中task_id 表示子任务编号,V 表示值域,limit 表示最大询问次数。 – 你需要返回四元组(k_u, k_v, b_u, b_v) 表示你给出的直线L′ 的解析 式为y = ku kv x + bu bv 。 – 你需要保证ku 与bu 在long long 范围内,kv 与bv 在int 范围内,且 kv, bv > 0。你不需要保证给出的分数是既约分数。可以证明在本题的数据范 围下,总是存在这样的(ku, kv, bu, bv) 满足条件。 .在.最.终.测.试.时,.交.互.库.将.会.调.用T ≤104 .次Find .函.数。 – 你可以使用std::make_tuple(a,b,c,d) 来将a,b,c,d 打包成一个tuple。 你可以调用如下函数进行一次询问: • bool query(int x,int y); 第7 页 共10 页 第一试平原(plain) IOI2025 中国国家集训队集中培训 – 你需要保证0 ≤x, y ≤V ,在单组测试数据内该函数的调用次数不超过 limit。 – 当(x, y) ∈SL 时,函数返回true,否则返回false。 保证在满足题目条件和数据范围的情况下,最终测试时交互库的运行时间不会超过 200 ms,运行空间不会超过64 MiB。 .交.互.库.不.是.自.适.应.的,.即L .是.固.定.的,.不.会.随.着.交.互.过.程.改.变。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.我.们.提.供.的.交.互.库.参.考.实.现。.最.终.测.试.的.交.互.库.与 .样.例.交.互.库.有.一.定.不.同,.故.你.的.实.现.不.应.该.依.赖.样.例.交.互.库.实.现。 你需要在本题目录下使用如下命令编译得到可执行程序: g++ plain.cpp grader.cpp ‐o plain ‐O2 ‐‐std=c++14 ‐lm 1 对于编译得到的可执行程序: • 可执行文件将从标准输入读入以下格式的数据: – 第一行三个整数task_id, T, limit,分别表示子任务编号,测试数据组数和每 组测试数据的询问次数上限。接下来依次输入每组测试数据。 – 对于每组测试数据输入一行五个整数V, ku, kv, bu, bv,其中V 表示值域, ku, kv, bu, bv 表示直线L 的解析式为y = ku kv x + bu bv 。 – 你需要保证bu 在long long 范围内,ku, kv, bv 在int 范围内,且kv, bv > 0。 对于所有测试数据,保证存在这样的(ku, kv, bu, bv) 满足题目条件。 • 读入完成之后,交互库将会调用T 次Find 函数。 • 若每一组测试数据中你都在给定的询问次数内求出了正确的直线,交互库将在标 准输出流输出两行,第一行一个字符串Correct.,第二行一个整数,表示T 组 测试数据中query 调用次数的最大值。否则交互库会输出对应错误信息,并立 即停止程序。 【样例1 输入】 0 3 20 1 4 5 11 11 6 2 4 ‐11 15 17 5 3 4 2 15 4 5 4 【样例1 输出】 第8 页 共10 页 第一试平原(plain) IOI2025 中国国家集训队集中培训 Correct. 1 8 2 【样例1 解释】 task_id = 0 表示该组数据为样例。 这是第一组数据对应的函数图像。 图1: 第一组数据对应的函数图像 这是第二组数据对应的函数图像。 图2: 第二组数据对应的函数图像 这是第三组数据对应的函数图像。 【子任务】 对于所有测试数据,2 ≤V ≤109,1 ≤T ≤104,100 ≤limit ≤3, 666。 第9 页 共10 页 第一试平原(plain) IOI2025 中国国家集训队集中培训 图3: 第三组数据对应的函数图像 limit 子任务编号 分值 特殊性质 V T 1 10 ≤102 无 ≤10 = 110 2 20 A ≤109 ≤103 = 180 3 10 ≤105 ≤10 = 1, 111 4 15 ≤109 ≤500 = 3, 666 5 20 ≤105 = 102 无 ≤10 6 10 ≤109 = 180 7 15 ≤104 特殊性质A:保证直线L 是由y = a 1 bx 向上平移至多 2b 得到的,其中0 < b ≤V 。 【评分方式】 .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制。例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制都会导致相应测试点得0 分。选手只能在程序中 访问自己定义的和交互库给出的变量或数据,及其相应的内存空间。尝试访问其他位置 空间将可能导致编译错误或运行错误。 当你在每次Find 调用中,程序调用的query 函数次数不超过limit,且返回的L′ 均满足题目描述中的条件,即通过该测试点,否则该测试点不通过。只有你通过一个子 任务的所有测试点时,才能获得该子任务的所有分数。 .选.手.不.应.通.过.非.法.方.式.获.取.交.互.库.的.内.部.信.息,.如.试.图.与.标.准.输.入、.输.出.流.进.行.交 .互。.此.类.行.为.将.被.视.为.作.弊。 第10 页 共10 页