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

View as PDF

Submit solution

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 |i-j| is prime.

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

  • You will give Larry two distinct indices i and j (1 \le i, j \le N, i \ne j) such that |i-j| is prime
  • Larry will respond with the result of A_i \times A_j

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

Constraints

4 \le N \le 10^5

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 N.

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 1 \le i, j \le N, i \ne j, and |i-j| is prime. In response, you will be given A_i \times A_j on its own line.

If you believe you have the solution, you may output ! followed by a space-separated list of N integers A_1, A_2, \dots, A_N, the permutation A. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of N-1 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 N-1 questions, the interactor will respond with -1. 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

Comments

There are no comments at the moment.