Median Queries solution codeforces – There is a secret permutation pp (11-indexed) of numbers from 11 to nn

Median Queries solution codeforces

 

This is an interactive problem.

There is a secret permutation pp (11-indexed) of numbers from 11 to nn. More formally, for 1in1≤i≤n1p[i]n1≤p[i]≤n and for 1i<jn1≤i<j≤np[i]p[j]p[i]≠p[j]It is known that p[1]<p[2]p[1]<p[2].

In 11 query, you give 33 distinct integers a,b,ca,b,c (1a,b,cn1≤a,b,c≤n), and receive the median of {|p[a]p[b]|,|p[b]p[c]|,|p[a]p[c]|}{|p[a]−p[b]|,|p[b]−p[c]|,|p[a]−p[c]|}.

In this case, the median is the 22-nd element (11-indexed) of the sequence when sorted in non-decreasing order. The median of {4,6,2}{4,6,2} is 44 and the median of {0,123,33}{0,123,33} is 3333.

Can you find the secret permutation in not more than 2n+4202n+420 queries?

Note: the grader is not adaptive: the permutation is fixed before any queries are made.

Input Median Queries solution codeforces

The first line of input contains a single integer tt (1t1000)(1≤t≤1000) — the number of testcases.

The first line of each testcase consists of a single integer nn (20n100000)(20≤n≤100000) — the length of the secret permutation.

It is guaranteed that the sum of nn over all test cases does not exceed 100000100000.

Interaction Median Queries solution codeforces

For each testcase, you begin the interaction by reading nn.

To perform a query, output “? a b c” where a,b,ca,b,c is the 33 indices you want to use for the query.

Numbers have to satisfy 1a,b,cn1≤a,b,c≤n and aba≠b,bcb≠c,aca≠c.

For each query, you will receive a single integer xx: the median of {|p[a]p[b]|,|p[b]p[c]|,|p[a]p[c]|}{|p[a]−p[b]|,|p[b]−p[c]|,|p[a]−p[c]|}.

In case your query is invalid or you asked more than 2n+4202n+420 queries, the interactor will print “−1” and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you have determined the secret permutation, output “! p[1] p[2] … p[n]“. If the secret permutation is correct, the interactor will print “1“. Otherwise, the interactor will print “-1” and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

Hacks:

To hack, use the following format of test:

The first line should contain a single integer tt (1t10001≤t≤1000) — the number of testcases.

The first line of each testcase should contain a single integer nn (20n10000020≤n≤100000) — the length of the secret permutation.

The following line of should contain nn integers p[1],p[2],p[3],,p[n]p[1],p[2],p[3],…,p[n]p[1]<p[2]p[1]<p[2] and pp must be a permutation of integers from 11 to nn.

You must ensure that the sum of nn over all testcases does not exceed 100000100000.

Example Median Queries solution codeforces
input Median Queries solution codeforces

Copy Median Queries solution codeforces
1
20

6

9

1
output

Copy
? 1 5 2

? 20 19 2

! 9 10 19 7 16 18 11 14 15 6 20 8 17 4 5 3 12 2 13 1

Note

The secret permutation is {9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1}{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1}.

For the first query, the values of (a,b,c)(a,b,c) is (1,5,2)(1,5,2). Since p[1]=9p[1]=9p[5]=16p[5]=16 and p[2]=10p[2]=10. The return value is the median of {|916|,|1610|,|910|}{|9−16|,|16−10|,|9−10|} which is 66.

For the second query, the values of (a,b,c)(a,b,c) is (20,19,2)(20,19,2). Since p[20]=1p[20]=1p[19]=13p[19]=13 and p[2]=10p[2]=10. The return value is the median of {|113|,|1310|,|110|}{|1−13|,|13−10|,|1−10|} which is 99.

By some miracle, we have figured out that the secret permutation is {9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1}{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1}. We output it and receive 11 from the interactor, meaning that we have guessed the secret permutation correctly.

SOLUTION

Click here



Median Queries solution codeforces Splitting a String Into Descending Consecutive Values Minimum Adjacent Swaps to Reach the Kth Smallest Number Minimum Interval to Include Each Query


  1. What is Codeforces? What kind of a site/resource is it?
    Codeforces is a project joining people interested in and taking part in programming contests. On one hand, Codeforces is a social network dedicated to programming and programming contests. On the other hand, it is a platform where contests are held regularly, the participant’s skills are reflected by their rating and the former contests can be used to prepare. Codeforces constantly develops and we plan to improve the platform to give the participants the opportunity to organize their own contests, filling the project with learning content, developing Codeforces as a training and learning platform.
  2. What should I do to participate in contests? Is preliminary registration required?
    Contests are regularly held on Codeforces. Participating in them is free and open to everybody. Every month we organize approximately six contests. To participate, you have to be registered on the site (if you have an OpenID or a Gmail account, then you won’t even have to memorize the password) and register for the oncoming contest. Make sure that you are present in the list of the users, registered for the contest, before the registration ends. Usually, if you can’t take part in the contest officially (e.g. if it’s the contest for the second division and you are in the first one), then you can register for the contest to participate out of competition.
  3. What are the rules of the contests?
    They are usually held according to the original Codeforces rules. If it is specially stated, then the International Collegiate Programming Contest rules ACM-ICPC or some other modifications can be used. In brief, on the contests held by Codeforces rules you write solutions to the problems that are tested during the contest on a very small number of tests. Those who have passed that set of solution tests, their authors can block (refuse to resend the solutions of this task in future even if they find a mistake). Such authors receive the opportunity to look through the sources of other contestants, look for mistakes there and suggest the tests on which these solutions do not work. Thus, you can hack somebody else’s solution and earn points through it.
    After the contest all the solutions that have passed the pretests and haven’t been hacked are tested on the final set of tests. The value of a task decreases during the contest (the faster you solve the problem, the more points you receive), unsuccessful hacks take off the points and the successful ones add them. Please take a look at the detailed version of the rules before participating in the contest.
  4. What languages can I use to solve problems here? Are there any problem solving examples?
  5. I would like to organize a Codeforces round with my problems. What should I do to achieve that? Are the authors entitled to get any reward?
    Do you want to organize a round? That’s great! We are very pleased to hear that. Please, read the post.
  6. What other rules are on Codeforces?
    We don’t have a clear Great Codeforces Code of Conduct. However, of course, here you should behave in accordance with traditional rules of behavior in public places and theme groups. The following rules are, of course, necessary to follow:
    • Don’t create more than one account, if you have forgotten the password, use the password reminding system.
    • Do not use harsh, rude or misleading handle.
    • Do not use anybody photo except yours. It is uncultured and could confuse Codeforces users.
    • Don’t be rude, don’t insult other participants and administration, try to be polite and pleasant to communicate with.
    • When you take part in individual contests, don’t talk about the problems with other contestants, don’t use somebody else’s code or insert it into your solutions. If the contest is a team one, discuss the tasks only with the teammates.
    • Don’t try to destabilize the site’s and the checking system’s work. Your programs should only interact with the console (for the problems with the standard input and output) or the input and output data files.
    • Don’t publish or spread your solutions and solution ideas during the contest.
  7. Which technical details are useful to know about the Codeforces’ testing system?
    The Codeforces system resembles classical Online Judges. The solutions are tested on the tests prepared beforehand (or the hacks suggested by other participants). As a result, you receive verdicts, the meaning of which is clear from the title.
  8. It should be specially noted that Codeforces does not have the “Presentation Error” verdict, this situation is regarded as “Wrong Answer”. All the suspicious verdicts (testing error etc.) are not considered while evaluating the results. That is also true for the solutions that had fallen on test 1 (in the problems containing more than one test).
  9. What are the rating and the divisions?
    When the contesters take part in Codeforces contest, they raise or lower their rating that reflects their ability to solve the tasks. The rating is a modification of Elo rating, several details can be read in a fuller form. According to the rating, the contestants are split into two divisions: the second one (the weaker one, amateurs) and the first one (the stronger one, pros).
  10. The contestants who don’t take part in contests and those whose rating is below 1900 belong to the second division. The 1900+ rating means that you’re part of the first division. Usually two types of contests are held on Codeforces: for the second division contestants (the first division contestants can take part there out of competition) and for both divisions. The first contest type contains simpler and learning-oriented tasks.
  11. What is contribution?
    The votes for the posts and comments of a user change his/her contribution. The contribution is intended to show the usefulness of the community user. The contribution counting system is imperfect; in future the rules for its calculation will be changed.
  12. What blog posts are useful to take a look at?
  13. I’ve noticed that the site contains the solutions of all the contestants and the previous contests’ tests. How is it allowed to use them?
    In fact, we publish materials from the past contests and they can be used, for example, for individual lessons. Using the materials on other Online Judges, public contests, etc. is prohibited. Be sure to

    read the license before using the materials.

    In order to view someone else’s solution, just click on his id on the page “Status”. From the page with the list of tasks you can go to the list of correct decisions for the given task. At the bottom of the “Status” pages (and others with the lists of decisions) there is an option of sorting the solutions on different criteria.
 

Leave a Comment