Reconstruct a Permutation Introduction

Suppose that you are handed a random permutation of n objects.
The permutation is sealed in a box, so you have no idea which of the n! possible ones it is.
If you managed to apply the permutation to n distinct objects, you could immediately deduce its identity.
However, you are only allowed to apply the permutation to length-n binary vectors, which means you'll have to apply it several times in order to recognize it.
Clearly, applying it to the n vectors with only one 1 does the job, but if you're clever, you can do it with log(n) applications.
The code for that method will be longer, though...

This is an experimental challenge where your score is a combination of code length and query complexity, meaning the number of calls to an auxiliary procedure.
The spec is a little long, so bear with me.

The Task

Your task is to write a named function (or closest equivalent) f that takes as inputs a positive integer n, and a permutation p of the first n integers, using either 0-based or 1-based indexing.
Its output is the permutation p.
However, you are not allowed to access the permutation p directly.
The only thing you can do with it is to apply it to any vector of n bits.
For this purpose, you shall use an auxiliary function P that takes in a permutation p and a vector of bits v, and returns the permuted vector whose p[i]th coordinate contains the bit v[i].
For example:

P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]


You can replace "bits" with any two distinct values, such as 3 and -4, or 'a' and 'b', and they need not be fixed, so you can call P with both [-4,3,3,-4] and [2,2,2,1] in the same call to f.
The definition of P is not counted toward your score.

Scoring

The query complexity of your solution on a given input is the number of calls it makes to the auxiliary function P.
To make this measure unambiguous, your solution must be deterministic.
You can use pseudo-randomly generated numbers, but then you must also fix an initial seed for the generator.

In this repository you'll find a file called permutations.txt that contains 505 permutations, 5 of each length between 50 and 150 inclusive, using 0-based indexing (increment each number in the 1-based case).
Each permutation is on its own line, and its numbers are separated by spaces.
Your score is byte count of f + average query complexity on these inputs.
Lowest score wins.

Extra Rules

Code with explanations is preferred, and standard loopholes are disallowed.
In particular, individual bits are indistinguishable (so you can't give a vector of Integer objects to P and compare their identities), and the function P always returns a new vector instead of re-arranging its input.
You can freely change the names of f and P, and the order in which they take their arguments.

If you are the first person to answer in your programming language, you are strongly encouraged to include a test harness, including an implementation of the function P that also counts the number of times it was called.
As an example, here's the harness for Python 3.

def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()


In some languages, it is impossible to write such a harness.
Most notably, Haskell does not allow the pure function P to record the number of times it is called.
For this reason, you are allowed to re-implement your solution in such a way that it also calculates its query complexity, and use that in the harness.
J, 44.0693 22.0693 = 37 15 + 7.06931

If we can't call P on i. n, we can at least call P on each bit of i. n separately. The number of invocations of P is &gt;. 2 ^. n (&lceil;log2&thinsp;n&rceil;). I believe this is optimal.

f=:P&amp;.|:&amp;.#:@i.


Here is an implementation of the function P which uses the permutation vector p and saves the number of invocations into Pinv.

P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 &gt; # ~. y    NB. make sure y is binary
 p { y
)


Here is a testing harness that receives a permutation and returns the number of invocations of p:

harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)


And here is how you can use it on the file permutations.txt:

NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'


Explanation

The short explanation is already provided above, but here is a more detailed one. First, f with spaces inserted and as an explicit function:

f =: P&amp;.|:&amp;.#:@i.
f =: 3 : 'P&amp;.|:&amp;.#: i. y'


Read:


  Let f be P under transposition under base-2 representation of the first y integers.


where y is the formal parameter to f. in J, the parameters to a  (function) are called x and y if the verb is dyadic (has two parameters) and y if it is monadic (has one parameter).

Instead of invoking P on i. n (i.e. 0 1 2 ... (n - 1)), we invoke P on each bit position of the numbers in i. n. Since all permutations permute in the same way, we can reassemble the permutated bits into numbers to get a permutation vector:


i. y – integers from 0 to y - 1.
#: y – y represented in base 2. This is extended to vectors of numbers in the natural way. For instance, #: i. 16 yields:

0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

#. y – y interpreted as a base 2 number. Notably, this is the inverse to #:; y ~: #. #: always holds.
|: y – y transposed.
u&amp;.v y – u under v, that is vinv u v y where vinv is the inverse to v. Notice that |: is its own inverse.
P y – the function P applied to each vector in y by definition.