DMOPC '20 Contest 6 P5 - Jennifer's Math Mystery

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 7.0s
Memory limit: 256M

Authors:
Problem types

When does Jennifer do math?

This is one of the world's largest unsolved problems at the moment, with dozens of world-renowned scientists struggling to find the answer to this question. You, a brilliant young researcher, have been working on this problem for the past six months. You've come up with a list of N integers representing times you think Jennifer might do math.

However, one day, you find that your list has been stolen by the very Jennifer herself! You managed to strike a deal with Jennifer, and she has agreed to answer some peculiar questions about the list of numbers. In one question, you can ask her about:

  1. the bitwise AND of the i-th and j-th numbers, or
  2. the bitwise OR of the i-th and j-th numbers

for some indices (i, j), and she will respond with the correct result.

Quirky as she is, Jennifer only permits questions on M unordered pairs of indices (a_i, b_i), which she will tell you before you start asking questions. She guarantees that you are able to determine a unique list of numbers by asking questions about only these M pairs, regardless of the numbers in the list itself. However, since Jennifer is on a tight schedule (perhaps she needs to do math), she will answer no more than 2N-1 questions.

Given these critical conditions, please write a program to recover your list of numbers!

Interaction

This is an interactive problem. The first line contains 2 integers N (1 \le N \le 10^5) and M (0 \le M \le 5 \times 10^5), the length of the list and the number of permitted pairs of indices respectively.

The next M lines each contain 2 integers a_i and b_i (1 \le a_i, b_i \le N), representing a permitted pair of indices (a_i, b_i). In particular, it may be the case that a_i = b_i. It is guaranteed that you are able to determine a unique list of numbers by only asking questions about these M pairs, regardless of the numbers in the list itself.

You will then begin interaction with Jennifer. If you would like to ask a question, you may output ? i & j (followed by a \n character) to ask the first type of question, or ? i | j (followed by a \n character) to ask the second type of question. For each of these questions, the pair (i, j) or (j, i) must be permitted. After either of these questions, Jennifer will respond with an integer (followed by a \n character), the answer to that question.

Otherwise, you may output ! followed by a space-separated list of N integers in the range [0, 10^9] (followed by a \n character), representing your guess of the list of numbers. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of 2N-1 questions.

For all cases, it is guaranteed that all of the correct numbers in the list are integers in the range [0, 10^9]. Also, the list is fixed before the interaction begins and will not depend on your choice of questions.

For 30\% of available marks, it is guaranteed that 1 \le N \le 10^3, M = \frac{N^2 - N}{2}, and all pairs (i, j) where i < j are permitted.

If at any point you attempt an invalid question (such as invalid output format or a prohibited pair of indices), Jennifer will respond with -1. You should terminate your program immediately after receiving this feedback, or you may receive an arbitrary verdict. If you exceed the limit of 2N-1 questions or 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.

In this case, Jennifer stole your list which had the numbers [3, 1, 4, 1, 5].

5 9
1 2
1 3
1 5
2 3
2 4
2 5
3 4
3 5
4 5
>>> ? 1 & 3
0
>>> ? 2 | 5
5
>>> ? 4 | 3
5
>>> ? 1 & 2
1
>>> ? 4 | 5
5
>>> ! 3 1 4 1 5

Sample Explanation

This interaction would receive an Accepted verdict, since it correctly guessed the list of numbers using only the permitted pairs and it did not exceed the limit of 2N-1 questions. Note that, for example, the questions ? 1 & 4, ? 4 | 1, and ? 1 & 1 are not permitted since (1, 4) and (1, 1) are not among the list of permitted pairs to ask questions about.


Comments


  • 1
    maxcruickshanks  commented on April 28, 2022, 1:15 a.m.

    Since the original data were weak, 6 test cases that are not connected graphs were added, and all submissions were rejudged.