# Comparing Plants SOLUTIONS IOI 2020

Page Contents

## 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

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

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.

(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.