A. Anu Has a Function

1500
  • Quiz
  • AC
  • 解説
    • f(a,b) = a&(~b)
    • 最終的な値は、先頭のa0と、それ以外（順不同）で決まる。ではどれを先頭に持ってくればいいか？
    • 先頭の値のbit=1, それ以外のbit=0であるようなbitの桁があれば、最終的な値もそのbitは1にできる
    • 各桁ごとにbitの出現回数を求め、それが1であるものから、先頭にすべき値が分かる

サンプルテストケース

3
11 4 11

answer
4 11 11

int main(){
    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    // 各ビットの出現回数
    VI C(35);
    for(ll a : A){
      auto bs = bitset<35>(a);
      rep(i,35){
        C[i] += bs[i];
      }
    }

    ll bit_one_pos = -1;
    for(int i=35-1; i>=0; i--){
      if(C[i]==1){
        bit_one_pos = i;
        break;
      }
    }

    // この場合はどの順番にしても答えが変わらない
    if(bit_one_pos==-1){
      print_vector(A);
      return 0;
    }

    // 誰が先頭
    int head_index = -1;
    rep(i,N){
      ll a = A[i];
      auto bs = bitset<35>(a);
      if(bs[bit_one_pos]==1) head_index=i;
    }

    // index
    VI I;
    rep(i,N)I.push_back(i);
    swap(I[head_index], I[0]);
    
    VI Ans;
    for(ll idx : I){
      Ans.push_back(A[idx]);
    }
    print_vector(Ans);

    return 0;
}