Lineup Queries
플래티넘 V의견: 0
There is a line of cows, initially (i.e. at time \(t = 0\)) containing only cow
\(0\) at position \(0\) (here, a cow is at position \(k\) if there are \(k\) cows in
front of it). At time \(t\) for \(t=1,2,3,\dots\), the cow at position 0 moves to
position \(\lfloor t/2\rfloor\), every cow in positions
\(1\dots \lfloor t/2\rfloor\) moves forward one position, and cow \(t\) joins the
line at the end of the line (position \(t\)).
Answer \(Q\) (\(1\le Q\le 10^5\)) independent queries, each of one of the following
types:
- At what position is cow \(c\) immediately after time \(t\) (\(0\le c\le t\le 10^{18}\))?
- Which cow is at position \(x\) immediately after time \(t\) (\(0\le x\le t\le 10^{18}\))?
Problem credits: Agastya Goel
SCORING
- Input 3: \(Q\le 1000, t\le 100\)
- Input 4: \(t\le 5000\)
- Inputs 5-8: All queries are of type 1.
- Inputs 9-12: All queries are of type 2.
Problem credits: Agastya Goel
The first line contains \(Q\), the number of queries.
The next \(Q\) lines each contain three integers specifying a query either of the
form "1 c t" or "2 x t."
Output the answer to each query on a separate line.
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
평가 및 의견
Lineup Queries
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Lineup Queries