#2766. 「ROI 2017 Day 1」四轴飞行器编程

内存限制:512 MiB 时间限制:2000 ms 题目类型:交互
上传者: Planet6174

题目描述

译自 ROI 2017 Day1 T1. Программирование квадрокоптеров

本题的数据是 HeRaNO 配的,有锅请找他

控制四轴飞行器的程序是一个长度为 n 的字符串,仅由 () 组成,( 表示爬升 1 米,) 表示下降 1 米。这 n 条指令依次编号为 1\ldots n
如果飞行器开始时在地上,完整执行了一遍程序后,飞行器刚好回到地面,并且在整个过程中,程序没有让它往地底下钻(换句话说,当飞行器在地面上时,仍然接到了 ) 指令),这个程序就是正确的。例如,()(())((())) 是正确的程序。((( 是不正确的,因为程序结束后飞行器位于地面上方 3 米处,())( 也是不正确的,因为第三条指令要求飞行器往地底下钻。
现在飞行器里有一个正确的程序。你想知道这个程序,但这个程序没法导出。还好,飞行器支持一种特殊调试模式。在此模式下,装有程序的四轴飞行器可以回答请求。每个请求包含两个整数 l, r(1\le l\le r\le n) 。对于每个请求,它会回答 \texttt{Yes} \texttt{No} ,表示:如果将原程序只留下指令 l 到指令 r ,程序还是否正确。你希望使用调试模式来得到完整程序。

请编写一个程序,与模拟调试模式的交互器进行交互,并最终输出完整程序。

交互过程

你可以编写一个函数 getProgram() 并在程序开始包含 grader.h 来完成交互过程。该函数无返回值,也没有参数。或者直接编写一个完整程序来完成交互。

你需要先从标准输出流中获得一个整数 n ,表示四轴飞行器程序中的命令条数。

你可以向标准输出中输出询问和回答,形式如下:

  • 对于询问一段程序是否合法,你需要先输出一个字符 ?,后跟两个整数 l,r ,表示如果只留下指令 l 到指令 r 的程序,字符,整数之间用一个空格隔开。如果只留下指令 l 到指令 r 程序仍然正确,交互器会向标准输出中输出 \texttt{Yes} ,否则会输出 \texttt{No}
  • 对于回答整个程序,你需要先输出一个字符 !,后跟一个序列 c_1c_2\ldots c_n ,表示这个程序。! 与序列之间用一个空格隔开。其中 c_i 只能是 ()

在回答之后,你应该结束程序。保证四轴飞行器程序在交互过程中不会改变。

交互过程中,你的询问数不能超过一个值 k

样例

program.png

注:给出的例子中为了按步表示交互器的输出和你的输出,因此添加了多余的空白行,但是你的程序并不需要输出这些空白行。

数据范围与提示

子任务编号 分值 n k
1 21 2\le n\le 16 k=150
2 28 2\le n\le 100 k=10^4
3 26 2\le n\le 1000
4 25 2\le n\le 5\times 10^4 k=10^5