Summary
Your problem remains NP-hard, despite the fact that the algorithm can choose the function $f$. Consequently, no, you should not expect a polynomial-time algorithm.
The problem is at least as hard as the subset-sum problem. Fortunately, subset-sum is one of the easier NP-hard problems, so if your problem instance is small enough, you might be able to use algorithms for subset sum to solve your problem.
Problem statement
I'm going to reformulate your problem statement, so we are all on the same page:
Input: integers $m,n, a_1,\dots,a_m$; and access to an oracle, as follows:
Oracle: has secret values $x_1,\dots,x_m \in \{1,\dots,n\}$; when provided a function $f:\{1,2,\dots,n\}\to \mathbb{N}$, the oracle outputs the value $a_1 f(x_1) + \dots + a_m f(x_m)$
Goal: find $x_1,\dots,x_m$
An algorithm
You could use algorithms for subset-sum to help solve your problem, using the following strategy.
Let $\delta_1$ denote the function so that $\delta_1(1)=1$ and $\delta_1(j)=0$ for all $j \ne 1$. Send $\delta_1$ to the oracle, and call the result $k_1$, i.e., $k_1 = a_1 \delta_1(x_1) + \dots + a_m \delta_1(x_m)$. Notice that $k_1$ is a sum of the a subset of the $a_i$'s, namely, those where $x_i=1$. In other words, $k_1=\sum_{i \in S_1} a_i$ where $S_1=\{j : x_j=1\}$. So, feed $a_1,\dots,a_m$ and $k_1$ into an algorithm for the subset sum algorithm, and ask it to find a subset of the $a_i$'s that sums to $k_1$. If this subset sum problem has a unique solution, then the result will tell you which $x_i$'s have the value 1.
Next, let $\delta_2$ denote the function so that $\delta_2(2)=1$ and $\delta_2(j)=0$ for all $j \ne 2$. Send $\delta_2$ to the oracle, and call the result $k_2$. Do the same thing, using a subset-sum solver to find a subset of $a_i$'s that sum to $k_2$; if this solution is unique, that will be the set of $x_i$'s that have the value 2.
Repeat, for $\delta_1,\dots,\delta_n$, until you have learned all the value of all of the $x_i$'s.
If you're lucky, the subset-sum problem has a unique solution at each stage, and after solving $n$ subset-sum problems you can read off the values of the $x_i$'s. If you're unlucky, it has multiple solutions, and now you might need to consider all combinations of solutions to find a combination where the subsets are disjoint.
(Incidentally, once you've queried the oracle on $\delta_1,\dots,\delta_n$, you can predict the response of the oracle on any other function, so there's not much point in querying it again. This shows that $n$ queries to the oracle suffice; we'll never need more than that.)
The problem is NP-hard
Here is a reduction to show that the problem is as hard as subset sum. In particular, we'll show that the special case of your problem where $n=2$ is as hard as subset sum. Suppose we have a subset sum instance, namely numbers $a_1,\dots,a_m$ and a target $t$. We'll show how to use any algorithm for your problem to solve this subset sum instance.
We will implement a sneaky oracle, which behaves as follows: when provided a function $f:\{1,2\} \to \mathbb{N}$, it returns the value
$$f(1) \cdot (a_1 + \dots + a_m) + (f(2)-f(1)) \cdot t.$$
Notice that the sneaky oracle doesn't have a particular set of values $x_1,\dots,x_m$ in mind. Nonetheless, if there is a subset of the $a_i$'s that sums to $t$, the responses from the sneaky oracle would be equivalent to what we would obtain if we had an ordinary oracle where the $x_i$'s were 2 for all $i$ in that subset and 1 otherwise; and if there is no subset of the $a_i$'s that sums to $t$, the responses from the sneaky oracle are not equivalent to any ordinary oracle (for any value of the $x_i$'s).
Now, ask the purported algorithm for your problem to work with this sneaky oracle and find values for the $x_i$'s. If the algorithm for your problem finds a solution for the $x_i$'s, that yields a solution for the subset sum problem (simply include the $a_i$'s where $x_i=2$ in the subset). If the algorithm for your problem doesn't find a solution for the $x_i$'s, there is no subset of the $a_i$'s that sums to $t$.
(Strictly speaking, this shows the case where $n=2$ is hard. However, one can show that increasing $n$ does not make the problem any harder. Thus, the case where $n=\sqrt{m}$ is also hard.)