16794번 - Xylophone 서브태스크다국어언어 제한함수 구현

Xylophone is a musical instrument which is played by striking wooden bars. A single wooden bar will always sound the same pitch, so a xylophone consists of bars with various pitches.

JOI-kun bought a xylophone consisting of N wooden bars. The bars are lined up in a row and numbered 1 through N from left to right. The bar with number i (1 ≤ i ≤ N) sounds a pitch of height A_i (1 ≤ A_i ≤ N). Different bars sound different pitches. He knows that the bar with the lowest pitch has a smaller number than the bar with the highest pitch.

Because JOI-kun does not know which bar sounds which pitch, he is going to study the pitch of the bars.

JOI-kun has a peculiar sense of sound; when he hears multiple sounds simultaneously, he can tell the difference between the heights of the highest pitch and the lowest pitch. He can strike a lump of bars at a time and hear their sounds. That is, for integers s and t (1 ≤ s ≤ t ≤ N), he can strike the bars with numbers s through t simultaneously, to know the difference between the maximum and the minimum among As, As+1, . . . , A_t.

He wants determine the pitches of the bars within 10 000 tries of striking.

You should implement the following function solve to find the pitches of the bars.

• solve(N)
  • N: the number of bars.
  • This function is called exactly once for a test case.

Your program can call the following function prepared by the grader.

• query(s, t)
  • This function returns the difference between the maximum and the minimum among the sounds of bars in the specified interval.
    • s, t: s is the first number and t is the last number in the interval of bars to strike. That is, you strike all the bars with number at least s and at most t.
    • It must hold that 1 ≤ s ≤ t ≤ N.
    • You cannot call query more than 10 000 times.
    • If some of the above conditions are not satisfied, your program will be judged Wrong Answer.
• answer(i, a)
  • Your program should answer the pitches of the bars using this function.
    • i, a: these mean that you answer A_i is a, where A_i is the height of the pitch of bar i.
    • It must hold that 1 ≤ i ≤ N.
    • You cannot call this function for the same value of i more than once.
    • You must call this function exactly N times before the function solve terminates.
    • If some of the above conditions are not satisfied, your program will be judged Wrong Answer.
    • If some of the pitches you answered are different from the actual ones, your program will be judged Wrong Answer.

An example of communication for N = 5, [A₁, A₂, A₃, A₄, A₅] = [2, 1, 5, 4, 3] is shown below.

• 1 ≤ A_i ≤ N (1 ≤ i ≤ N)
• A_i ≠ A_j (1 ≤ i < j ≤ N)
• For i and j with A_i = 1 and A_j = N, it holds that i < j.

The sample grader reads the input in the following format:

• line 1: N
• line 1 + i (1 ≤ i ≤ N): A_i

If your program answer the pitches correctly when solve terminates, the sample grader prints Accepted : Q with Q being the number of calls to query.

If your program is judged Wrong Answer, it prints Wrong Answer.

• grader.cpp xylophone.cpp xylophone.h
• sample-01.txt