最短コード105B

id:namasute0さんが超短いコードを書いていた。
私も追いつかねばなるまい。

malloc/freeを使わない方法はないのか。
よく考えれば、このプログラムで使用する巨大な配列は、すでに選んだかそうでないかのチェックに使っているに過ぎない。trueを意味するマジックナンバーをインプット毎に設定して、その値以外はfalseとみなせば、配列の初期化をせずに使いまわすことができる。インプットに同じ入力が含まれることは「ないだろう」と都合良く考えれば、そのマジックナンバーをインプットの値にしておけば良い。インプットの最大値が500000なので、int型でも問題ない値である。

というわけで最終的なコードはこれ。
メモリ消費量とか時間が微妙に違うのだが、namasuteさんもこんなかんじじゃないかなぁと思う。

i,s['~~~'];
main(a,n){
  for(;scanf("%d",&n)+n;printf("%d\n",a))
    for(a=i=0;i++<n;)
      s[a+=a>i&&s[a-i]-n?-i:i]=n;
}