問題一覧 > 通常問題

No.1509 Swap!!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 87
作問者 : 👑 qand / テスター : mine691 oliverx3 yuto1115
お気に入りにしたユーザー ProblemId : 6207 / 自分の提出
問題文最終更新日: 2021-05-13 23:13:30
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 295 (順位表) の他の問題:

Problem Statement

You can perform the following $2$ operations, in any order and any number of times, on a permutation $P=(P_1,P_2,\ldots,P_N)$ of length $N$ obtained by rearranging the positive integers from $1$ to $N$ inclusive.

・Choose an integer $i$ satisfying $1\le i \le N-A$, and swap the values of $P_i$ and $P_{i+A}$.

・Choose an integer $i$ satisfying $1\le i \le N-B$, and swap the values of $P_i$ and $P_{i+B}$.

Your final goal is to sort $P$ in ascending order. Determine whether the goal can be achieved regardless of the initial state of $P$.

You are given $T$ test cases; find the answer for each of them.

Constraints

  • $1\le T\le 5\times10^4$
  • $2\le N\le 10^{18}$
  • $1\le A,B< N$
  • All input values are integers

    • Input

    $T$
$case_1$
$\vdots$
$case_T$
    Each test case is given in the following format. 
    $N$ $A$ $B$

    Output

    Print $T$ lines.

    On the $i$-th line, print YES if the goal can be achieved for the $i$-th test case, and NO otherwise.

    Sample

    Sample 1
    Input
    3
3 1 2
4 2 2
10000000000000000 1122334455667788 9988776655443322
    Output
    YES
NO
NO

    Consider the $1$st test case.

    For example, if the initial state is $3\ 1\ 2$, then

    $3\ 2\ 1$ (swap the $2$nd and $3$rd elements)

    $1\ 2\ 3$ (swap the $1$st and $3$rd elements)

    sorts it in ascending order.

    The other permutations of length $3$ can also be sorted in ascending order by appropriate swaps, so print YES.

    In the $2$nd test case, for example, if the initial state is $4\ 3\ 2\ 1$, it cannot be sorted in ascending order no matter how you rearrange it.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。