Algorithm Analysis
Flatten the circle such that it becomes $$$n$$$ rows of length $$$nm$$$ with vertical sections numbered from $$$0$$$ to $$$nm-1$$$ that loops on the end. We say that the position of an arc is $$$x$$$ if the left endpoint of the arc is at section $$$x$$$. Indices are taken modulo $$$nm$$$ at all times. Moving arcs right is equivalent to rotating them clockwise, and moving arcs left is equivalent to rotating them counter-clockwise.
Notice that if we shift arc 0 right and the display increases, then the leftmost section of arc 0 had no other arcs in the same section. Thus, if we shift arc 0 right again and the display does not increase, we are certain that there was another arc at that position, so we shift arc 0 left. We now enter the detection stage to find any arc that coincides with arc 0 (of which there exists at least 1) at this position. Let's note down this positions as $$$x$$$.
Let $$$S$$$ be the set of arcs that we do not know the positions of yet (this set initially contains all arcs from 1 to $$$N-1$$$) and $$$T$$$ and $$$F$$$ be an empty sets. $$$T$$$ will be the set of all candidate arcs (those that may coincide here) and $$$F$$$ will contain all arcs that we have shifted leftwards. Take all elements in $$$S$$$ and put them in $$$T$$$, and pick half of the elements in $$$S$$$ and add them to the set $$$F$$$. We now shift all elements in $$$F$$$ left.
We move arc 0 left to check if any arc is at position $$$x-1$$$.
If there is, then we know that an arc that initially coincided at $$$x$$$ lies in $$$F$$$. In this case, we set $$$T$$$ to $$$T \cap F$$$ (elements of $$$T$$$ that are in $$$F$$$), pick half of the elements in $$$T$$$ to move right and remove those from $$$F$$$.
If no arc is at position $$$x-1$$$, then the arc we are looking for lies in $$$T \ \backslash \ F$$$ (elements in $$$T$$$ that are not in $$$F$$$). We set $$$T$$$ to be $$$T \ \backslash \ F$$$ and pick half of $$$T$$$ to move left and add those to $$$F$$$. We then shift arc 0 right and recurse.
When we have narrowed $$$T$$$ to exactly 1 arc, we know where exactly that arc is now. We shift that arc left such that its right endpoint is at $$$x-2$$$ so that it does not cover position $$$x-1$$$, which we may still need for future tests. Now we remove the arc found from $$$S$$$ and leave the detection stage and continue searching for the other arcs.
Once we have found all $$$n-1$$$ other arcs, we find the relative position to arc 0 and print them as the final output.
Query Analysis
Whenever we shift arc 0 right and are not in the detection stage, we use 1 shift. This occurs at most $$$2nm-m$$$ times because it takes up to $$$nm-m$$$ shifts right to find the first position where arc 0 coincides, and another $$$nm$$$ to traverse the entire circle again to find all of the arcs.
Whenever we enter the detection stage, we find one arc and use $$$2$$$ shifts initially when we move arc 0 right then left, yielding a total of $$$2n-2$$$ such shifts. Each binary search requires $$$2 \log |T|$$$ shifts of arc 0 (left and right), so across the $$$n-1$$$ detection stages this is at most $$$2n\log n$$$ when summed across all stages.
The way we perform the binary search is quite important here. Performing it in a naive manner (e.g. shifting half left, test and shifting them back) can use up to $$$n^2$$$ queries.
Instead, we set the number of elements that move in / out of $$$F$$$ at each iteration of the binary search to be the smaller half. This way we can guarantee that the number of shifts done by the candidate arcs is at most the total number of candidate arcs in the first place. This becomes $$$\frac{n(n-1)}{2}$$$ since we start with $$$n-1$$$ candidate arcs and reduce that number by 1 after each detection stage.
When we shift each of the arcs left by $$$m$$$ or $$$m+1$$$ (depending on whether they were in $$$F$$$ when we narrowed it down to 1 arc), we use at most $$$(n-1)(m+1) = nm+n-m-1$$$ shifts.
Thus in total, we use at most $$$2nm-m+2n-2+2n\log n + \frac{n(n-1)}{2} + nm+n-m-1$$$ shifts. For $$$n=100,m=20$$$, this is less than $$$13000$$$, which is much lower than the query limit of $$$15000$$$.
Other Comments
The limit was set higher than the provable bound to allow for other possible solutions. At least $$$1$$$ tester found a different solution that used around $$$13500$$$ queries.
Some other optimizations that empirically improve the number of queries:
Instead of using arc $$$0$$$ as the detector, we can randomly pick one of the $$$n$$$ arcs as the detector arcs.
At the very beginning, we perform some constant number of random shifts of the arcs (e.g. $$$300$$$ to $$$400$$$ random shifts). This helps to break up long groups of arcs that overlap, which speeds up the initial $$$nm$$$ search.
The official solution, augmented with these optimizations uses well below $$$11500$$$ queries and is very consistent for non-handcrafted test cases.