マージソートの要領で解く方法を紹介します。

\(N = 1\) の場合、何も質問する必要はなく、答えは \(\{1\}\) です。

\(N = 2\) の場合、予想として数列 \(\{1, 2\}\) を聞きます。答えの数列は \(\{1, 2\}\) か \(\{2, 1\}\) なので、回答が 2 であれば \(\{1, 2\}\), 0 であれば \(\{2, 1\}\) とできます。

\(N > 2\) において、答えとなる数列を \(A\) とした時、\(A\) の右半分に属する数と左半分に属する数の2グループに、 \(1\) から \(N\) を分けることを考えます。
\(i = 2, 3, \ldots, N\) について、予想として、左半分を \(1\) , 右半分を \(i\) とした数列を聞きます。よって、質問回数は \(N - 1\) 回です。
\(N = 2\) の場合と同様に考えると、答えは

• 0 (\(1\) が右、\(i\) が左)
• 1 (\(1, i\) が共に右 or \(1, i\) が共に左)
• 2 (\(1\) が左、\(i\) が右)

の3通りがあり得ます。
ここで、\(N > 2\) を考えているので、数列の右半分、左半分はそれぞれ空ではありません。よって、回答として \(0\) か \(2\) を受け取る \(i\) が必ず存在します。
回答として \(0\) を受け取った場合、\(1\) を回答された \(i\) と \(1\) は右半分に、\(0\) を回答された \(i\) は左半分に属します。
回答として\(2\) を受け取った場合、\(1\) を回答された \(i\) と \(1\) は左半分に、\(2\) を回答された \(i\) は右半分に属します。

以上から、\(N - 1\) 回の質問で、\(1\) から \(N\) を半分に分けることができました。

部分列についても、部分列の外を適当な数で埋めることで、同様にして右半分に属する数と左半分に属する数に分けることができます。

よって、再帰的に以上の工程を行うことで、答えの配列を計算することができます。
質問回数は、マージソートと同様の計算を行うことで、高々 \(N\log_2 N\) 回であることがわかります。\(N = 100\) の時 \(N\log_2 N < 700\) なので、全ての問題に正解することができました。