시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
9 초 | 512 MB | 29 | 9 | 7 | 28.000% |
Have you ever been on a long road journey? AAA (the American Automobile Association) has a tool for long road trips. It’s called a TripTik, and it follows the highways, showing points of interest.
You are building a TripTik app, which allows users to see what’s on their route. It models a highway as a straight line, and points of interest as points along that line. All points have an integer coordinate as well as a unique integral weight. Your app provides a viewport, which can scale in and out. Also, to prevent the display from becoming too cluttered, only a small number of the points with the highest weights are shown. The initial viewport is centered at $0.0$, and shows from $-1.0$ to $1.0$ on the line.
There are three valid operations for changing your viewport:
There is an important caveat: Your TripTik app will not render all points of interest in a given viewport; instead, it will only render a certain number of points in the viewport with the highest weights. The remaining points with lower weight are not visible, and therefore are not valid targets for the recenter operation.
For each point of interest, determine the minimum number of operations needed to go from the starting viewport to a viewport where that point of interest is centered and visible. Consider each point of interest independently.
The first line of input contains two integers $n$ ($1 \le n \le 10^5$) and $k$ ($1 \le k \le 4$), where $n$ is the number of points, and $k$ is the maximum number of points visible in the viewport.
Each of the next $n$ lines contains a single integer $x$ ($|x| \le 10^8$ , $x \ne 0$). These are the points of interest. The weight of each point is equal to its position in the list, with lower weights earlier in the list. All points will be distinct.
Output $n$ lines, each with a single integer, indicating the minimum number of operations necessary to get from the starting viewport to a viewport which is centered on the corresponding input point and can see that point. Output $-1$ if this isn’t possible. The order of output lines should correspond to the order of inputs for which they’re the answer.
4 2 100 4 1 3
-1 5 1 3
ICPC > Regionals > North America > Southeast USA Regional > 2020 Southeast USA Regional Programming Contest O번
ICPC > Regionals > North America > Mid-Central Regional > 2020 Mid-Central Regional Programming Contest I번
ICPC > Regionals > North America > Pacific Northwest Regional > 2020 ICPC Pacific Northwest Region > Division 1 I번
ICPC > Regionals > North America > Mid-Atlantic Regional > 2020 Mid-Atlantic USA Regional Contest H번
ICPC > Regionals > North America > South Central USA Regional > 2020 South Central USA Regional Contest O번