問題一覧 > 通常問題

No.2968 Final MIGISITA Strike

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.525秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 5
作問者 : twitteryou / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 11531 / 自分の提出
問題文最終更新日: 2024-11-16 18:02:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 453 (順位表) の他の問題:

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 streamer's character hits the $i$-th $(1 \leq i \leq N)$ allied character, its speed increases by $A_i$.
  • When the streamer's character hits the $i$-th $(1 \leq i \leq M)$ enemy character, its speed decreases by $B_i$.
  • When the streamer's character hits a wall, it bounces off with an angle of reflection equal to the angle of incidence, and its speed decreases by $C$. However, when it hits a corner, its speed decreases by $2C$ and it moves back along the path it came from.

  • 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$
    

  • $3 \leq H,W \leq 10^9$
  • $1 \leq N,M \leq 5 \times 10^4$
  • $1 \leq S \leq 10^{18}$
  • $1 \leq A_i,B_j,C \leq 10^9(1 \leq i \leq N,1 \leq j \leq M)$
  • $0 < X,x_i,a_j < H (1 \leq i \leq N,1 \leq j \leq M)$
  • $0 < Y,y_i,b_j < W (1 \leq i \leq N,1 \leq j \leq M)$
  • The coordinates at which the characters are placed are all distinct.
  • All inputs are integers.
  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。