For each plant I (0≤i≤n−1), Hazel contrasted plant I with each of the following k−1 plants in clockwise request, and recorded the number r[i] meaning the number of these plants k−1 are taller than plant I. In this way, each worth r[i] relies upon the overall statures of some k sequential plants.
For instance, assume n=5, k=3 and i=3. The following k−1=2 plants in clockwise request from plant i=3 would be plant 4 and plant 0. In the event that plant 4 was taller than plant 3 and plant 0 was shorter than plant 3, Hazel would record r=1.
You may accept that Hazel recorded the qualities r[i] accurately. In this manner, there is at any rate one arrangement of particular statures of plants steady with these qualities.
You were solicited to analyze the statures from q sets of plants. Unfortunately, you don’t approach the presentation. Your lone wellspring of data is Hazel’s scratch pad with the worth k and the arrangement of qualities r, … , r[n−1].
For each pair of various plants x and y that should be analyzed, figure out which of the three after circumstances happens:
Plant x is unquestionably taller than plant y: in any design of particular statures h, … , h[n−1] reliable with the cluster r we have h[x]>h[y].
Plant x is unquestionably shorter than plant y: in any arrangement of particular statures h, … , h[n−1] steady with the exhibit r we have h[x]<h[y].
The correlation is uncertain: neither of the past two cases applies.
You should execute the accompanying system:
void init(int k, int r)
k: the quantity of back to back plants whose statures decide every individual worth r[i].
r : a variety of size n, where r[i] is the quantity of plants taller than plant I among the following k−1 plants in clockwise request.
This methodology is called precisely once, before any calls to compare_plants.
int compare_plants(int x, int y)
x,y : marks of the plants to be looked at.
This system should return:
1 if plant x is unquestionably taller than plant y,
−1 if plant x is unquestionably shorter than plant y,
0 if the examination is uncertain.
This system is called precisely q times.
Think about the accompanying call:
init(3, [0, 1, 1, 2])
Suppose the grader calls compare_plants(0, 2). Since r=0 we can promptly induce that plant 2 isn’t taller than plant 0. Along these lines, the call should bring 1 back.
Suppose the grader calls compare_plants(1, 2) next. For all potential designs of statures that fit the limitations above, plant 1 is shorter than plant 2. In this manner, the call should return −1.
Think about the accompanying call:
init(2, [0, 1, 0, 1])
Suppose the grader calls compare_plants(0, 3). Since r=1, we realize that plant 0 is taller than plant 3. Hence, the call should bring 1 back.
Suppose the grader calls compare_plants(1, 3) next. Two arrangements of statures [3,1,4,2] and [3,2,4,1] are both steady with Hazel’s estimations. Since plant 1 is shorter than plant 3 out of one arrangement and taller than plant 3 in the other, this call should bring 0 back.
0≤r[i]≤k−1 (for all 0≤i≤n−1)
There exists at least one arrangements of unmistakable statures of plants predictable with the exhibit r.
(5 focuses) k=2
(14 focuses) n≤5000,2⋅k>n
(13 focuses) 2⋅k>n
(17 focuses) The right response to each call of compare_plants is 1 or −1.
(11 focuses) n≤300,q≤n⋅(n−1)2
(15 focuses) x=0 for each call of compare_plants.
(25 focuses) No extra imperatives.
The example grader peruses the contribution to the accompanying configuration:
line 1: n k q
line 2: r r … r[n−1]
line 3+i (0≤i≤q−1): x y for the I-th call to compare_plants
The example grader prints your answer in the accompanying organization:
line 1+i (0≤i≤q−1): return estimation of the I-th call to compare_plants