問題一覧 > 通常問題

No.1386 Range add Simulation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 4
作問者 : 蜜蜂蜜蜂 / テスター : cardano1016cardano1016 MitarushiMitarushi
0 ProblemId : 5805 / 出題時の順位表
問題文最終更新日: 2021-02-08 08:53:03

問題文

ミツバチ君は$\ N\ $要素からなる数列$\ A\ $を持っています。
$A_i\ $を$\ A\ $の$\ i\ $番目の要素とします。現在$\ 1 \leq i \leq N\ $を満たす全ての整数$\ i\ $について$\ A_i=0\ $が成り立っています。

ミツバチ君はこれから$\ Q\ $回にわたり、操作を行います。$\ i\ $回目の操作は以下のように表せます。

    $C_i=1\ $の場合 : $S_i \leq j \leq N\ $を満たす全ての整数$\ j\ $に対し、$A_j\ $に$\ (j-S_i+1)^2\ $を加算する。
    $C_i=2\ $の場合 : $1 \leq j \leq S_i\ $を満たす全ての整数$\ j\ $に対し、$A_j\ $に$\ (S_i-j+1)^2\ $を加算する。

$Q\ $回の操作後、ミツバチ君はあなたに$\ N\ $要素からなる数列$\ B\ $を渡してきました。
$B_i\ $を$\ B\ $の$\ i\ $番目の要素とします。現在$\ 1 \leq i \leq N\ $を満たす全ての整数$\ i\ $について$\ B_i=0\ $が成り立っています。

あなたの目標は、$A\ $と$\ B\ $を一致させることです。
また、あなたは以下の操作を合計$\ 410000\ $回まで行うことができます。

    操作$\ 1$ : $1 \leq i \leq N\ $を満たす整数$\ i\ $を一つ選ぶ。$B_i\ $に$\ 1\ $を足す。
    操作$\ 2$ : $1 \leq i \leq N\ $を満たす整数$\ i\ $を一つ選ぶ。$B_i\ $から$\ 1\ $を引く。
    操作$\ 3$ : $1 \leq i,j \leq N\ $かつ$\ |i-j| \leq 1\ $を満たす整数$\ i,j\ $を一つずつ選ぶ。$B_i\ $に$\ B_j\ $を足す。
    操作$\ 4$ : $1 \leq i,j \leq N\ $かつ$\ |i-j| \leq 1\ $を満たす整数$\ i,j\ $を一つずつ選ぶ。$B_i\ $から$\ B_j\ $を引く。

操作$\ 3,4\ $の際、$\ i=j\ $となるように$\ i,j\ $を選んでもいいことに気を付けてください。

ただし、ミツバチ君は文句が多いので、操作の過程で$\ |B_i| > 10^{17}\ $となるような整数$\ i\ $が存在するような操作を行ってもいけません。

本問題の制約下で、ミツバチ君が文句を言わないような$\ A\ $と$\ B\ $を一致させる操作法は存在することが示されるので、それを出力してください。
条件を満たす出力が複数存在する場合、どれを出力しても正解となります。

入力

$N\ \ Q$
$C_1\ \ S_1$
$C_2\ \ S_2$
$\vdots$
$C_Q\ \ S_Q$

  • $1 \leq N \leq 10^5$
  • $1 \leq Q \leq 5 \times 10^4$
  • $1 \leq C_i \leq 2(1 \leq i \leq Q)$
  • $1 \leq S_i \leq N(1 \leq i \leq Q)$
  • 入力は全て整数

出力

$1\ $行目に操作の回数である$\ X\ $を出力してください。
問題文より$\ X\ $は$\ 0 \leq X \leq 410000\ $を満たす整数である必要があります。

$2\ $行目から$\ X\ $行に渡り、操作の方法を出力してください。$2 \leq i \leq X+1\ $を満たす整数$\ i\ $について、$i\ $行目の出力は$\ i-1\ $番目の操作を表すとします。

操作$\ 1\ $の場合、以下のように出力してください。

1 i
これは出力の$\ i\ $で操作$\ 1\ $を選んだこと、すなわち$\ B_i\ $に$\ 1\ $を足した操作を行なったことを示します。
よって、$i\ $は$\ 1 \leq i \leq N\ $を満たす整数である必要があります。

操作$\ 2\ $の場合、以下のように出力してください。

2 i
これは出力の$\ i\ $で操作$\ 2\ $を選んだこと、すなわち$\ B_i\ $から$\ 1\ $を引いた操作を行なったことを示します。
よって、$i\ $は$\ 1 \leq i \leq N\ $を満たす整数である必要があります。

操作$\ 3\ $の場合、以下のように出力してください。

3 i j
これは出力の$\ i, j\ $で操作$\ 3\ $を選んだこと、すなわち$\ B_i\ $に$\ B_j\ $を足した操作を行なったことを示します。
よって、$i,j\ $は$\ 1 \leq i,j \leq N\ $かつ$\ |i-j| \leq 1\ $を満たす整数である必要があります。

操作$\ 4\ $の場合、以下のように出力してください。

4 i j
これは出力の$\ i, j\ $で操作$\ 4\ $を選んだこと、すなわち$\ B_i\ $から$\ B_j\ $を引いた操作を行なったことを示します。
よって、$i,j\ $は$\ 1 \leq i,j \leq N\ $かつ$\ |i-j| \leq 1\ $を満たす整数である必要があります。

以上より、出力は$\ X+1\ $行からなります。
出力の各行において、最後に改行してください。

サンプル

サンプル1
入力
4 3
1 3
2 1
1 4
出力
9
1 2
3 1 2
3 3 2
1 3
3 4 3
3 4 3
2 3
1 4
4 2 1

$A\ $は以下のように変化します。

$0,0,0,0 \rightarrow 0,0,1,4 \rightarrow 1,0,1,4 \rightarrow 1,0,1,5$

また、$B\ $は以下のように変化します。

$0,0,0,0 \rightarrow 0,1,0,0 \rightarrow 1,1,0,0 \rightarrow 1,1,1,0 \rightarrow 1,1,2,0 \rightarrow 1,1,2,2 \rightarrow 1,1,2,4 \rightarrow 1,1,1,4 \rightarrow 1,1,1,5 \rightarrow 1,0,1,5$

よって、操作後の$\ A,B\ $は共に$\ 1,0,1,5\ $となるので、この出力は正解となります。

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