Problem I
Bracket Guessing

This is an interactive problem.

There is a hidden bracket string $s$ of size $n$. You can ask up to $n$ queries of the form $?$ $l$ $r$, and the judge will tell you whether the contiguous substring from position $l$ to position $r$ is a regular bracket sequence. Find the longest contiguous substring of $s$ that is a regular bracket sequence.


A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters ‘1’ and ‘+’ between the original characters of the sequence. For example, bracket sequences “()()”, “(())” are regular (the resulting expressions are: “(1)+(1)”, “((1+1)+1)”), and “)(” and “(” are not.


The judge will start by outputting a line with a single integer $n$ ($1\le n \le 10^4$) —the size of the bracket sequence.

You can then ask at most $n$ queries. For each query, output a single line of the form $?$ $l$ $r$ ($1 \le l \le r \le n$). The judge will then output $1$ if the substring from position $l$ to $r$, inclusive, is a regular bracket sequence, and $0$ otherwise.

Make sure to flush the output after printing every query, or you will receive a Time Limit Exceeded verdict. In order to flush the output, use:

  • fflush(stdout) in C++

  • System.out.flush() in Java

  • stdout.flush() in Python

  • For other languages, see the documentation.

Once you have found the longest substring $[l, r]$ that is a regular bracket sequence, output $!$ $l$ $r$. If there are no substrings that are regular bracket sequences, print $!$ $none$. Printing the answer does not count towards your limit of $n$ queries.

If there are multiple solutions, you may choose any.

The strings in the samples are $)(()))(()$, $)(($, and $()()$, respectively.

Read Sample Interaction 1 Write
? 1 8
? 8 9
? 2 5
? 1 6
? 6 7
! 2 5
Read Sample Interaction 2 Write
? 1 2
? 2 3
! none
Read Sample Interaction 3 Write
? 1 2
? 3 4
! 1 4

Please log in to submit a solution to this problem

Log in