Monkey Bread

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type

Steven, the monkey, is baking banana bread today!

The recipe for banana bread calls for N ingredients numbered from 1 to N. The recipe can be modelled as an array A of length N, where A_i describes the amount for ingredient i. Moreover, Steven's special banana bread recipe is a permutation of the first N positive integers!

Unfortunately, Steven lost the recipe and doesn't remember the ordering!

Fortunately, Steven had sent his recipe to his friend Tony for safekeeping. However, being a monkey, Tony obfuscated the recipe and tells Steven that he can only ask for the number of inversions present in some subarray of array A from l to r inclusive satisfying 1 \le l < r \le N. Due to how impatient Tony is, he informs Steven that he can only ask up to N questions. Help Steven recover the recipe so he can have dessert tonight!

A pair of indices i and j in the array A is considered an inversion if i < j and A[i] > A[j].


1 \le N \le 3\,000

Array A is a permutation of the first N positive integers.


This is an interactive problem.

You will start by reading in a single integer N, the number of ingredients in the bread.

Note: The grader is NOT adaptive.

After reading N, you can start interacting with the interactor.

To ask a query, you must output in the form ? l r to standard output. You will then read a single integer from standard input, which is the number of inversions in the contiguous subarray from l to r.

To validate your final answer, you must output ! followed by a space, then N space-separated numbers, which are the elements of the array A. Your program should then terminate immediately.

The output must be flushed after every line is printed, including the last line. In C/C++, you can use fflush(stdout) or cout << endl, in Java you can use System.out.flush(), and in Python you can use sys.stdout.flush().

At any time, if you ask an invalid query or exceed N queries, the interactor will print -1. Once you read -1, terminate your program immediately and you will receive a Wrong Answer verdict. Failure to terminate your program may result in an undefined result.

Sample Interaction 1

Note: Do not actually print out <<< and >>>. >>> means that the interactor printed out the line, and <<< means that you printed out the line.

>>> 5
<<< ? 3 4
>>> 0
<<< ? 1 5
>>> 5
<<< ? 2 4
>>> 0
<<< ! 3 2 4 5 1

Explanation for Sample Interaction 1

Our array is [3, 2, 4, 5, 1] and there are 5 inversions. The pairs of indices that form inversions are (1, 2), (1, 5), (2, 5), (3, 5), (4, 5).

Sample Interaction 2

>>> 3
<<< ? 1 2
>>> 0
<<< ! 1 2 3


There are no comments at the moment.