시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 (추가 시간 없음) | 1024 MB | 300 | 53 | 46 | 16.547% |
Hilbert's Hotel has infinitely many rooms, numbered 0, 1, 2, ⋯. At most one guest occupies each room. Since people tend to check-in in groups, the hotel has a group counter variable $G$.
Hilbert's Hotel had a grand opening today. Soon after, infinitely many people arrived at once, filling every room in the hotel. All guests got the group number 0, and $G$ is set to 1.
Ironically, the hotel can accept more guests even though every room is filled:
You have to write a program to process the following queries:
1 k
- If $k \geq 1$, then $k$ people arrive at the hotel. If $k = 0$, then infinitely many people arrive at the hotel. Assign the group number $G$ to the new guests, and then increment $G$ by 1.2 g x
- Find the $x$-th smallest room number that contains a guest with the group number $g$. Output it modulo $10^9 + 7$, followed by a newline.3 x
- Output the group number of the guest in room $x$, followed by a newline.In the first line, an integer $Q$ ($1 \leq Q \leq 300\,000$) denoting the number of queries is given. Each of the next lines contains a query. All numbers in the queries are integers.
1 k
queries, $0 \leq k \leq 10^9$.2 g x
queries, $g < G$, $1 \leq x \leq 10^9$, and at least $x$ guests have the group number $g$.3 x
queries, $0 \leq x \leq 10^9$.Process all queries and output as required. It is guaranteed that the output is not empty.
10 3 0 1 3 2 1 2 1 0 3 10 2 2 5 1 5 1 0 3 5 2 3 3
0 1 0 9 4 4
If you know about "cardinals," please assume that "infinite" refers only to "countably infinite." If you don't know about it, then you don't have to worry.
University > KAIST > 2019 KAIST 9th ICPC Mock Competition F번
Contest > Open Cup > 2019/2020 Season > Stage 5: Grand Prix of Korea F번