pseong

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

알고리즘/알고리즘 문제풀이

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

pseong 2022. 6. 26. 17:27
 

Problem - D - Codeforces

 

codeforces.com

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

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

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

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

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

'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글

Educational Codeforces Round 117 (Rated for Div. 2) E. Messages  (0) 2022.06.27
Educational Codeforces Round 117 (Rated for Div. 2) D. X-Magic Pair  (0) 2022.06.27
Codeforces Round #801 (Div. 2) D2. Tree Queries (Hard Version)  (0) 2022.06.22
Codeforces Round #802 (Div. 2) E. Serega the Pirate  (0) 2022.06.21
AtCoder Beginner Contest 256 F - Cumulative Cumulative Cumulative Sum  (0) 2022.06.21
'알고리즘/알고리즘 문제풀이' Related Articles more
Comments