超初心者が競プロに挑む

初心者からの競プロ練習記録

ARC021B解いてみた

解説を読んで、自分のやり方と違ったので載せておきます。
xorには結合法則が成り立つことと、自分自身にxorをすると、0になることを利用して、A_0の高次ビットから0と決め打ちして、整合性を確認しながらビットを埋めていけば自然に辞書順で最小となります。

#include <cstdio>
#include <cstring>
#define MAX_L 100000

using namespace std;

int B[MAX_L+10];
int A[MAX_L+10];

int main() {
  int L;
  scanf("%d", &L);

  for(int i=0;i<L;++i) {
    scanf("%d", &B[i]);
  }

  memset(A, 0, sizeof(A));

  for(int i=30;i>=0;--i) {
    int test;
    for(test=0;test<2;++test) {
      int next_bit = test;
      for(int j=0;j<L;++j) {
        int b_bit=(B[j] >>i) & 1;
        next_bit = b_bit xor next_bit;
      }
      if(next_bit == test) {
        break;
      } else {
        if(test == 1) {
          printf("-1\n");
          return 0;
        }
      }
    }
    A[0] |= (test<<i);
  }

  for(int i=1;i<L;++i) {
    A[i] = A[i-1] xor B[i-1];
  }

  for(int i=0;i<L;++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}