Comparing Plants SOLUTIONS IOI 2020

Comparing Plants SOLUTION

2020 International Olympiad in Informatics Day 1 (Mirror)

Hazel the botanist visited an uncommon display in the Singapore Botanical Gardens. In this show, n plants of particular statures are put all around. These plants are named from 0 to n−1 in clockwise request, with plant n−1 alongside plant 0. 

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[3]=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[0], … , 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[0], … , 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[0], … , 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. 
 
Execution subtleties 
 
You should execute the accompanying system: 
 
Duplicate 
 
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. 
 
Duplicate 
 
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. 
 
Models 
 
Model 1 
 
Think about the accompanying call: 
 
Duplicate 
 
init(3, [0, 1, 1, 2]) 
 
Suppose the grader calls compare_plants(0, 2). Since r[0]=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. 
 
Model 2 
 
Think about the accompanying call: 
 
Duplicate 
 
init(2, [0, 1, 0, 1]) 
 
Suppose the grader calls compare_plants(0, 3). Since r[3]=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. 
 
Requirements 
 
2≤k≤n≤200000 
 
1≤q≤200000 
 
0≤r[i]≤k−1 (for all 0≤i≤n−1) 
 
0≤x<y≤n−1 
 
There exists at least one arrangements of unmistakable statures of plants predictable with the exhibit r. 
 
Subtasks 
 
(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. 
 
Test grader 
 
The example grader peruses the contribution to the accompanying configuration: 
 
line 1: n k q 
 
line 2: r[0] r[1] … 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

Leave a Comment