Plants

Comparing Plants (plants)

Hazel the botanist visited a special exhibition in the Singapore Botanical Gardens. In this exhibition,

plants of distinct heights are placed in a circle. These plants are labelled from to

in

clockwise order, with plant

beside plant .

For each plant (

), Hazel compared plant to each of the next

plants in

clockwise order, and wrote down the number

denoting how many of these

plants are taller

than plant . Thus, each value

depends on the relative heights of some consecutive plants.

For example, suppose

,

and

. The next

plants in clockwise order from

plant

would be plant and plant . If plant was taller than plant and plant was shorter

than plant , Hazel would write down

.

You may assume that Hazel recorded the values

correctly. Thus, there is at least one

configuration of distinct heights of plants consistent with these values.

You were asked to compare the heights of pairs of plants. Sadly, you do not have access to the

exhibition. Your only source of information is Hazel's notebook with the value and the sequence of

values

.

For each pair of different plants and that need to be compared, determine which of the three

following situations occurs:

Plant

is definitely taller than plant

in any configuration of distinct heights

consistent with the array we have

.

Plant

is definitely shorter than plant

in any configuration of distinct heights

consistent with the array we have

.

The comparison is inconclusive: neither of the previous two cases applies.

Implementation details

You should implement the following procedures:

void init(int k, int[] r)

the number of consecutive plants whose heights determine each individual value

.

an array of size
, where
is the number of plants taller than plant among the next
plants in clockwise order.
This procedure is called exactly once, before any calls to compare_plants.
Plants (1 of 3)

int compare_plants(int x, int y)
, : labels of the plants to be compared.
This procedure should return:
if plant is definitely taller than plant ,
if plant is definitely shorter than plant ,
if the comparison is inconclusive.
This procedure is called exactly times.
Examples
Example 1
Consider the following call:
init(3, [0, 1, 1, 2])
Let's say the grader calls compare_plants(0, 2). Since
we can immediately infer that
plant is not taller than plant . Therefore, the call should return .
Let's say the grader calls compare_plants(1, 2) next. For all possible configurations of heights
that fit the constraints above, plant is shorter than plant . Therefore, the call should return
.
Example 2
Consider the following call:
init(2, [0, 1, 0, 1])
Let's say the grader calls compare_plants(0, 3). Since
, we know that plant is taller
than plant . Therefore, the call should return .
Let's say the grader calls compare_plants(1, 3) next. Two configurations of heights
and
are both consistent with Hazel's measurements. Since plant is shorter than plant
in one configuration and taller than plant in the other, this call should return .
Constraints
(for all
)
There exists one or more configurations of distinct heights of plants consistent with the array
Plants (2 of 3)

.

Subtasks

1. (5 points)

2. (14 points)

,

3. (13 points)

4. (17 points) The correct answer to each call of compare_plants is or

.

5. (11 points)

6. (15 points)

for each call of compare_plants.

7. (25 points) No additional constraints.

Sample grader

The sample grader reads the input in the following format:

line :

line :

line

(

):

for the -th call to compare_plants

The sample grader prints your answers in the following format:

line

(

return value of the -th call to compare_plants.
Plants (3 of 3)

Input / Output on this judge

This is the IOI function-implementation task plants adapted to standard input / output. Instead of implementing the function, read its arguments from standard input and print the returned value(s) to standard output, exactly as the official grader below does (its internal anti-cheat checks have been removed). You may also simply submit the grader together with your own implementation of the function.

Function signature (plants.h):

#include <vector>

void init(int k, std::vector<int> r);
int compare_plants(int x, int y);

Reference I/O driver (official grader, sanitized):

#include "plants.h"
#include <cstdio>
#include <cassert>
#include <vector>

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
    assert(scanf("%d%d%d", &n, &k, &q) == 3);
    r.resize(n);
    answer.resize(q);
    for (int i = 0; i < n; i++) {
        int value;
        assert(scanf("%d", &value) == 1);
        r[i] = value;
    }
    x.resize(q);
    y.resize(q);
    for (int i = 0; i < q; i++) {
        assert(scanf("%d%d", &x[i], &y[i]) == 2);
    }
    fclose(stdin);

    init(k, r);
    for (int i = 0; i < q; i++) {
        answer[i] = compare_plants(x[i], y[i]);
    }

    for (int i = 0; i < q; i++) {
        printf("%d\n", answer[i]);
    }

    fclose(stdout);

    return 0;
}

rip 작성

출처 IOI 2020