Bittijono

#include <iostream>
#include <math.h>
int main() {
	int n;
	int bits[4] = {0, 1, 1, 0};
	long long int v[100000];
	std::cin >> n;
	long long int cur;
	bool og = true;
	for (int i = 0; i < n; i++) {
		og = true;
		std::cin >> cur;
		while (cur > 4) {
			int m = pow(2, floor(log2(cur)));
			if (m == pow(2, log2(cur))) m = pow(2, log2(cur) - 1);
			cur -= m;
			og = !og;
		}
		v[i] = bits[(int)cur - 1];
		if (!og) v[i] = !v[i];
	}
	for (int i = 0; i < n; i++) {
		std::cout << v[i] << std::endl;
	}
	return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED