Bittijono

#include <iostream>
 
int main() {
  /*
  bit in index i in second half is negation of bit in index i on first half
  index of first: i
  index of second: i + 2^n, where 2^n <= i < 2^n+1
  So result is sum of bits in i, % 2
  */
  int q;
  std::cin >> q;
  bool* res = new bool[q]; // false 0, true 1
  for (int i = 0; i < q; ++i) {
    long long bit;
    std::cin >> bit;
    --bit; // Why are the bits numbered from 1, instaed of from 0???
    // Calculate sum of bits
    bool sum = false; // whether sum is odd
    while (bit != 0) {
      sum = !sum;
      bit &= bit - 1;
      // bitwise and. Since bit is 2^a1 + 2^(a2) + ... + 2^(an), where a1>a2>...>an>=0,
      // bit - 1 is 2^a1 + 2^(a2) + ... + 2^a(n-1) + (2^(an) - 1)
      // = 2^a1 + 2^(a2) + ... + 2^a(n-1) + 2^an-1 + 2^an-2 + ... + 2^0
      // bitwise and will remove one bit
    }
    res[i] = sum;
  }
  for (int i = 0; i < q; ++i) {
    std::cout << (res[i] ? "1\n" : "0\n");
  }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED