No.2968 Final MIGISITA Strike
タグ : / 解いたユーザー数 5
作問者 :
Story
On a certain livestream, a legendary quote is born...???: "Everyone, here we are. It's time for the Final Lower-Right."
Problem Statement
On a smartphone screen with horizontal length $H$ and vertical length $W$, there are the streamer's character, $N$ allied characters, and $M$ enemy characters. From now on, we regard the smartphone screen as the $xy$-plane.
The four corners of the smartphone screen are $(0,0),(H,0),(H,W),(0,W)$, and the sides of the smartphone screen are walls. The streamer's character is placed at $(X,Y)$, the allied characters at $(x_i,y_i)(1 \leq i \leq N)$, and the enemy characters at $(a_i,b_i)(1 \leq i \leq M)$.
The speed of the streamer's character is initially $S$, and it is launched at $45$ degrees toward the lower right, that is, in the direction such that the value of the $Y$ coordinate decreases by $1$ when the value of the $X$ coordinate increases by $1$. The speed and the direction of travel change only when the following events occur.
When the speed of the streamer's character becomes $0$ or less, it stops at that spot. Find the stopping position of the streamer's character, the number of hits on allies, and the number of hits on enemies. However, if it does not stop, report that fact. Also, find the number of hits on allies and the number of hits on enemies each modulo $998244353$.
Characters other than the streamer's character do not move, and since all characters are small, characters do not hit each other unless their coordinates coincide.
Input
$H$ $W$ $N$ $M$ $S$ $C$ $X$ $Y$ $x_1$ $y_1$ $A_1$ $x_2$ $y_2$ $A_2$ $\vdots$ $x_N$ $y_N$ $A_N$ $a_1$ $b_1$ $B_1$ $a_2$ $b_2$ $B_2$ $\vdots$ $a_M$ $b_M$ $B_M$
Output
Let $(x_{STOP},y_{STOP})$ be the coordinates of the stopping position, $s$ the number of hits on allies, and $t$ the number of hits on enemies. Output them as follows.
Output the number of hits on allies and the number of hits on enemies each modulo $998244353$.
However, if it does not stop, output $-1$.
$x_{STOP}$ $y_{STOP}$ $s$ $t$
Sample
Sample 1
Input
4 3 1 1 6 1 1 2 2 1 3 3 2 2
Output
3 2 2 3
First, it hits the ally, and its speed becomes $9$.
After that, it hits walls $2$ times, and its speed becomes $7$.
After that, it hits the enemy, and its speed becomes $5$.
After that, it hits walls $3$ times, and its speed becomes $2$.
After that, it hits the ally, and its speed becomes $5$.
After that, it hits the enemy, and its speed becomes $3$.
After that, it hits a corner, and its speed becomes $1$.
After that, it hits the enemy, its speed becomes $-1$, and it stops.
It has hit allies $2$ times and enemies $3$ times, so output as shown above.
Sample 2
Input
3 3 1 1 5 1 1 2 2 1 100 2 2 100
Output
-1
In this case, the speed keeps increasing and it does not stop. Output $-1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。