Submission #72757752

---

Source Code Expand

#include<cstdio>
int q;
long long int l, r;
char res[5001000];
inline int popcount(unsigned long long int x) {
	x ^= x >> 32;
	x ^= x >> 16;
	x ^= x >> 8;
	x ^= x >> 4;
	x ^= x >> 2;
	x ^= x >> 1;
	return x & 1;
}
int main() {
	int tcn = 0;
	scanf("%d", &tcn);
	while (tcn--) {
		scanf("%d%lld%lld", &q, &l, &r);
		long long int ans = (r - l + 2) / 2;
		bool flag = false;
		if (l % 2 == 1 && r % 2 == 0) {
			if (popcount(l) == popcount(r)) {
				ans++;
			}
			else {
				long long int diff = l ^ r;
				int diffbit = 0;
				while (diff > 0) {
					diff >>= 1;
					diffbit++;
				}
				diffbit--;
				long long int diffsize = 1LL << diffbit;
				if (r - l < diffsize) {
					flag = true;
					ans++;
				}
			}
		}
		if (q == 0) {
			printf("%lld\n", ans);
		}
		else {
			if (flag) {
				long long int lpvt = popcount(l);
				long long int rpvt = popcount(r);
				for (long long int x = l; x <= r; x++) {
					if ((x ^ l) < (x ^ r)) {
						if (popcount(x) == lpvt) {
							res[x - l] = '1';
						}
						else {
							res[x - l] = '0';
						}
					}
					else {
						if (popcount(x) == rpvt) {
							res[x - l] = '1';
						}
						else {
							res[x - l] = '0';
						}
					}
				}
			}
			else {
				long long int pvt = popcount(l);
				if (r % 2 == 0) {
					pvt = popcount(r);
				}
				pvt %= 2;
				for (long long int x = l; x <= r; x++) {
					if (popcount(x) == pvt) {
						res[x - l] = '1';
					}
					else {
						res[x - l] = '0';
					}
				}
			}
			res[r - l + 1] = 0;
			puts(res);
		}
	}
	return 0;
}

Submission Info

Judge Result