Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- Codeforces Round 831 (Div. 1 + Div. 2)
- Good Bye 2022: 2023 is NEAR
- vue3
- 기본키 변경
- dart
- 2022
- Round 866
- E - Hanging Hearts
- 알고리즘 대회
- list_display
- 앳코더
- iupc
- 코드포스
- 카카오 API
- Div. 2
- Hello 2023
- idpiframe_initialization_failed
- django
- shake!
- 카카오 로그인
- 밑바닥부터 시작하는 딥러닝 1
- expand item
- 넥토리얼
- 레지스터
- 1557
- Flutter
- Graph Cost
- 인하대 프로그래밍 경진대회
- vue-google-login
- 리버싱
Archives
- Today
- Total
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:27Problem - 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 |
Comments