Submission #4061159

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>

#define MAX_N (100000)

int main(int argc, char *argv[]) {
  // read inputs
  int N, as[MAX_N];
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &as[i]);
  }

  // solve
  int us[MAX_N] = {}, ans = 0;
  // all as are smaller than 2^30
  // and thus use only the first 30 bits
  for (int k = 29; k >= 0; k--) {
    const int mask1 = 1 << k;     // 0..010..0
    const int mask2 = mask1 - 1;  // 0..001..1
    // calculate XOR
    int cur_xor = 0;
    for (int i = 0; i < N; i++) {
      cur_xor ^= as[i];
    }
    // printf("k = %d, cur_xor = %#08x\n", k, cur_xor);

    // check if kth LSB is 1
    if (cur_xor & mask1) {
      // printf("k( = %d)th bit is set. attempt removal.\n", k);
      // we need to remove this 1 from the xor result
      // look for an unused a that can be used
      // the a we're looking for has the form,
      //     31   k    0
      //     *...*10...0
      int i0 = -1;
      for (int i = 0; i < N; i++) {
        const int a = as[i];
        if (!us[i] && (a & mask1) != 0 && (a & mask2) == 0) {
          i0 = i;
          break;
        }
      }

      if (i0 >= 0) {  // found
        // printf("i = %d, as[i] = %#08x\n", i0, as[i0]);
        // if found subtract 1 from it and mark as used
        as[i0]--;
        us[i0] = 1;
        ans++;
      } else {  // not found
        // printf("could not remove the k( = %d)th bit. impossible.\n", k);
        // not possible
        ans = -1;
        break;
      }
    }
  }
  printf("%d\n", ans);

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:9:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:11:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &as[i]);
                        ^

Judge Result