Iosif Pinelis proved that, when a solution is guaranteed to exist, it can be found using finitely many queries. 

When a solution is not guaranteed to exist, then it may be impossible to decide whether or not it exists with finitely many queries. I could prove it for the special case $t = s$. Suppose that, after some $n$ queries, for every $j\in [n]$, the answer for query $x_j$ is $g(x_j)=x_j$ and the answer for query $y_j$ is $g^{-1}(y_j)=y_j$. Then, it is possible that $g(x)\equiv x$, in which case no solution exists.  However, it is also possible that $g(x)$ is slightly different than $x$ in some open interval that does not contain any $x_j$ or $y_j$. In this case a solution exists.

When $t<s$ and a solution is not guaranteed to exist, I do not know if it is possible to decide with finitely-many queries.


  [1]: https://en.wikipedia.org/wiki/Adversary_model