Codeforces Round #755 (Div. 2, based on Technocup 2022 Elimination Round 2) D. Guess the Permutation

Problem - D - Codeforces

먼저 전체 구간에 대한 쿼리를 날려서 전체 개수를 얻는다.

그리고 이분 탐색으로 쿼리를 날려서 i j k에서 i를 찾는다.

그리고 i+1 부터 n까지 쿼리를 날려서 전체 개수에서 얼마만큼 빠졌는지 구하면 j 위치를 알 수 있다.

그렇게 되면 k위치는 x*(x-1)/2 = k-j+1 가 되는 x값을 이분 탐색으로 찾으면 k가 구해진다.

총쿼리의 개수는 1 + logn + 1 이므로 최대 32개이다.