PKU 3444 Wavelet Compression

http://poj.org/problem?id=3444
数列をあるルールに従って繰り返し処理した結果が入力されるので、もとのを復元するというような問題。

入力は多いようだけれど、それにあわせて制限時間もそこそこちゃんとしているようです。

main(){
  int n;
  while(cin>>n,n){
    vector<int> in(n);
    rep(i,n){
      cin>>in[i];
    }
    for(int s=1;s<n;s*=2){
      vector<int> ba=in;
      rep(i,s){
        in[2*i]=(ba[i]+ba[i+s])/2;
        in[2*i+1]=(ba[i]-ba[i+s])/2;
      }
    }
    rep(i,n){
      if(i)cout<<' ';
      cout<<in[i];
    }
    cout<<endl;
  }
}