二分查找, 交互式问题, 括号匹配, 前缀和, 构造算法, 区间性质, 性质分析

题目描述

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

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

控制四轴飞行器的程序是一个长度为 $n$ 的字符串，仅由 ( 和 ) 组成，( 表示爬升 1 米，) 表示下降 1 米。这 $n$ 条指令依次编号为 $1\ldots n$。

如果飞行器开始时在地上，完整执行了一遍程序后，飞行器刚好回到地面，并且在整个过程中，程序没有让它往地底下钻（换句话说，当飞行器在地面上时，仍然接到了 ) 指令），这个程序就是正确的。例如，()(()) 和 ((())) 是正确的程序。((( 是不正确的，因为程序结束后飞行器位于地面上方 3 米处，())( 也是不正确的，因为第三条指令要求飞行器往地底下钻。

现在飞行器里有一个正确的程序。你想知道这个程序，但这个程序没法导出。还好，飞行器支持一种特殊调试模式。在此模式下，装有程序的四轴飞行器可以回答请求。每个请求包含两个整数 $l, r$ $(1\le l\le r\le n)$。对于每个请求，它会回答 Yes 或 No，表示：如果将原程序只留下指令 $l$ 到指令 $r$，程序还是否正确。你希望使用调试模式来得到完整程序。

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

交互过程

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

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

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

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

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

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

数据范围与提示