#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/f

Repovive

Guessing the Permutation via Median - Repovive Premier Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

3F. Guessing the Permutation via Median

2750 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Page 1

We can find the relative value of every three indices by asking one query. That means, when we have three indices $i, j, k$ ; we can find the order of $\{p_{i}, p_{j}, p_{k}\}$ by asking one query.

How?

If we ask these three indices as a query, we will receive the index $m$ such that $p_m$ equals their median value and the specified flag s.

We can see that any order of $\{p_{i}, p_{j}, p_{k}\}$ will be different in this two values (3 is the bigger one, 2 is the median and 1 is the smaller one):
$Median\ index = i, s = 1:$ the order of $\{p_{i}, p_{j}, p_{k}\} = \{2, 1, 3\}$
$Median\ index = i, s = 0:$ the order of $\{p_{i}, p_{j}, p_{k}\} = \{2, 3, 1\}$
$Median\ index = j, s = 1:$ the order of $\{p_{i}, p_{j}, p_{k}\} = \{3, 2, 1\}$
$Median\ index = j, s = 0:$ the order of $\{p_{i}, p_{j}, p_{k}\} = \{1, 2, 3\}$
$Median\ index = k, s = 1:$ the order of $\{p_{i}, p_{j}, p_{k}\} = \{1, 3, 2\}$
$Median\ index = k, s = 0:$ the order of $\{p_{i}, p_{j}, p_{k}\} = \{3, 1, 2\}$

So we can find their order by receiving these two values.

We can find the relative value of every three indices by asking one query. That means, when we have three indices $i, j, k$ ; we can find the order of $\{p_{i}, p_{j}, p_{k}\}$ by asking one query.

How?

If we ask these three indices as a query, we will receive the index $m$ such that $p_m$ equals their median value and the specified flag s.

So we can find their order by receiving these two values.