The optimal way to reverse engineer a binary classification problem I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it.

In a scenario very similar to popular binary classification machine learning contests, competitors are required to submit their answers to the test set containing N data points. The accuracy of the submission will be announced. The competitors can then submit a new answer, and the new accuracy will always be published, no matter improved or not.

If the competitor has no information about the test set at all, what is the optimal way (in the sense that the least submissions are needed) to crack the challenge?
Your problem is tackled in Vaishampayan, Query Matrices for Retrieving Binary Vectors Based on the Hamming Distance Oracle. Vaishampayan relates this problem to one considered in Lev and Yuster, On the size of dissociated bases, and the upshot (if I understand things correctly) is that a random test set of size $O(N/\log N)$ (for an appropriate hidden constant) would do if you don't care about carrying the decoding procedure efficiently. Vaishampayan describes a more structured solution using $o(N)$ tests which can be implemented efficiently.