## An Animal Contest 5 P2 (Hard Version) - Permutations & Primes

View as PDF

Points: 10
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types

This problem is a harder version of Permutations & Products. In this version, you can only ask questions where is prime.

Larry the magical panda is bored of eating bamboo cookies, so he challenges you to a game. He has a permutation of which he calls , and you have to guess the permutation by asking questions. The questions work as follows:

• You will give Larry two distinct indices and such that is prime
• Larry will respond with the result of

Larry allows you to ask at most questions. Can you guess the permutation and win the game?

#### Interaction

This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.

At first, you should read in a line containing the integer .

You will then start the interaction by proceeding with your questions. Each question should be formatted as ? i j followed by a \n character, with , , and is prime. In response, you will be given on its own line.

If you believe you have the solution, you may output ! followed by a space-separated list of integers , the permutation . You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of questions.

If at any point you attempt an invalid question (such as an invalid output format or a prohibited pair of indices), or you exceed the limit of questions, the interactor will respond with . You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict. If the final list you output is incorrect, you will receive a Wrong Answer verdict. Otherwise, you will receive a verdict of Accepted for the corresponding test case.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

#### Sample Interaction

>>> denotes your output. Do not print this out.

5
>>> ? 3 5
10
>>> ? 1 4
4
>>> ? 4 2
3
>>> ! 4 3 2 1 5