わはははは。>>747のヒントでオレは分かったぞ。
以下、並び替える前提でスマートな回答。

1. 1番目の囚人は適当に100枚ひっくり返す。セーフの確率は1/2。
2. セーフだったとして、表返したカードを左（右）端から数えて
　カード自身の番号となるように「横向きに」並び替える。
　伏せているカードは間を埋めるように「縦向きのまま」おいておく。
3. 2番目の囚人は自身の番号（2番目）に該当するところを見る。
　2番目のカードが横向きならそれを表替えせばクリア。
　2番目のカードが縦向きならどこにあるかは不明なので、
　縦向きのまま残っている100枚をひっくり返せばどれかが当たり。
4. あとは並び替えるまでもなく2番目と同様に繰り返せばよい。

これで絶対確率は1/2じゃうひょぉおおおおおお！！！！！

・・・・・・カードが正方形とか丸だったらどうしようorz。