레이팅 미적용소들이 한 줄로 서 있는데, 처음(즉, 시각 \(t = 0\))에는 소 \(0\)만이 위치 \(0\)에 서 있다 (여기서 어떤 소의 앞에 소가 \(k\)마리 있으면 그 소는 위치 \(k\)에 있다고 한다). 시각 \(t\) (\(t=1,2,3,\dots\))에, 위치 0에 있는 소는 위치 \(\lfloor t/2\rfloor\)로 이동하고, 위치 \(1\dots \lfloor t/2\rfloor\)에 있는 모든 소는 한 위치 앞으로 이동하며, 소 \(t\)가 줄의 맨 끝(위치 \(t\))에 합류한다.
다음 두 유형 중 하나인 \(Q\) (\(1\le Q\le 10^5\))개의 독립적인 쿼리에 답하라.
- 시각 \(t\) 직후, 소 \(c\)는 어느 위치에 있는가 (\(0\le c\le t\le 10^{18}\))?
- 시각 \(t\) 직후, 위치 \(x\)에는 어떤 소가 있는가 (\(0\le x\le t\le 10^{18}\))?
Problem credits: Agastya Goel
SCORING
- 입력 3: \(Q\le 1000, t\le 100\)
- 입력 4: \(t\le 5000\)
- 입력 5-8: 모든 쿼리가 유형 1이다.
- 입력 9-12: 모든 쿼리가 유형 2이다.
Problem credits: Agastya Goel
첫째 줄에 쿼리의 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각각 "1 c t" 또는 "2 x t" 형태의 쿼리를 지정하는 세 정수가 주어진다.
각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.
2
1 4 9
2 2 92
4Lineups immediately after various times:
t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9
Immediately after \(t=9\), the location of cow \(4\) is \(2\), and the cow located at position \(2\) is
\(4\).
22
1 0 9
1 1 9
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
1 9 9
2 0 9
2 1 9
2 2 9
2 3 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
2 9 9
1 0 1000000000000000000
2 0 10000000000000000001
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Silver