片方向リスト実装編 step 1 (paizaランク C 相当)

このメニューでは連結リストというデータ構造をそれぞれ実装します。その中でも前半は片方向リストと呼ばれるデータ構造を扱います。片方向リストは以下の操作をおこなえるデータ構造です。

・リストの先頭、末尾に要素を追加・削除する ... O( 1 )
・リストの特定の位置に定数個の要素を追加・削除する ... O( N )
・リストの特定の位置に K 個の要素を追加・削除する ... O( N + K )
・リストの特定の位置の要素を参照する ... O( N )

リスト構造に要素 A_1, A_2, A_3 をこの順で追加した場合、以下の画像のようになります。各ノードは開始ノードから順に一方向で連結され、終了ノードへと続きます。開始ノードおよび終了ノードは変更されません。片方向リストにおいて、各要素へのアクセスは基本的に先頭の要素から順にたどる必要があります。



まず要素を保持する配列( value )と次のノードのインデックスを保持する配列( next_ptr )を用意しましょう。両方とも 1,024 個の要素を持つ配列で、 value の先頭の要素の値と末尾の要素の値は - 1 、 next_ptr の先頭の要素の値は 1,023 、 next_ptr の末尾の要素の値は - 1 で初期化します。

また、末尾の要素の一つ前の要素のインデックスを保持する変数( back )と、 value に要素が入っていない最も小さいインデックスを保持する変数( empty_min_idx )を用意します。 back は 0 、 empty_min_idx は 1 で初期化します。

これらの必要な変数や配列をまとめると、以下の画像のようになります。



ここからがあなたのタスクです。 N 個の要素からなる数列 A が与えられます。上記の配列 value , next_ptr 、変数 back , empty_min_idx を用意した後、 A をそのまま出力してください。