https://www.acmicpc.net/problem/31865
문제 요약
- 원형 공간에 1부터 N까지 정해진 규칙에 의해서 추가
- 1은 1번째 자리
- 2부터는 특정숫자(p)에서 시계방향으로 특정번째 위치(x)에 추가
- N:30만
접근법
- 일일이 찾으면 물론 시간 초과
- 남은 공간으로 나머지 연산을 해도 물론 시간 초과
- 원형 공간이 1 ~ N 까지 한 줄로 나열 되었다고 가정
- 특정 숫자(p)의 위치는 꾸준히 업데이트 된다고 가정
- x 번째 빈 공간을 찾을때
- p에서 오른쪽에 공간이 충분한지 확인 -> 충분하면 오른쪽 어딘가
- 충분하지 않으면 왼쪽 어딘가 -> 이때 오른쪽 공간만큼 소모한 후 차이만큼 시작 지점에서 있을 것임
- 1 ~ N 까지 빈 공간의 개수를 유지함
- 특정 구간에서 빈공간의 개수가 몇 개인지
- 1번 위치부터 k 번째에 해당하는 빈 공간이 어디인지
- 특종 공간의 빈 공간은 사라지기도 함(업데이트)
- p와 x를 입력받았을 때
- p의 위치를 파악
- p의 위치에서 오른쪽에 빈 공간이 몇개인지 파악 -> a
- a >= x 이면 오른쪽에 있을테니 : find(왼쪽 빈 공간의 개수 + x)
- a < x이면 왼쪽에 있을테니 : find(x-오른쪽 빈 공간의 개수)
- 위치를 찾으면 빈 공간을 없애고
- 위치와 숫자를 매핑
newbieski