奇数行を左から右、偶数行を右から左へ読む長さ の蛇行経路を作る。経路で隣り合うマスは格子でも隣接する。
この経路を一次元配列と見て、未確定範囲を一つずつ縮めるバブルソートの比較を出力する。値を読む必要はない。右向きの辺には種類 、下向きには種類 、左向きには種類 を使う。左向きの場合は左側のマスの座標を指定する。
最初の段階は 回で経路を昇順にする。各行に必要な値はそろっているが偶数行は逆順なので、各偶数行を種類 のバブルソートで整列する。
操作数は
出力時間は 、経路保存は 。 では となる。 で、検査予算の分子は 。すべての演算は符号付き ビット整数に収まる。
サブタスク 1 の単純実装は経路全体へのバブルソートを 周行い、偶数行を修正する。 でそれぞれ 回となり制限内である。全範囲では確定済みの末尾を省いて最初の段階を 回に減らす。
チェッカーは操作を 空間に保存し、 時間で検査する。
Solution written by GPT6