fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <vector>
  4. #include <map>
  5. #include <set>
  6. #include <string>
  7. #include <algorithm>
  8. #include <iostream>
  9. #include <math.h>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. typedef pair<int,int> ii;
  16. typedef vector<int> vi;
  17. typedef vector<ii> vii;
  18.  
  19. int hmb(ull n){
  20. 	int ret = 0;
  21. 	while(n >= 2){
  22. 		n /= 2;
  23. 		ret++;
  24. 	}
  25. 	return ret;
  26. }
  27.  
  28. int hm1(ull n){
  29. 	int ret = 0;
  30. 	while(n > 0){
  31. 		if(n & 1 != 0) ret++;
  32. 		n >>= 1;
  33. 	}
  34. 	return ret;
  35. }
  36.  
  37. ull pw(int base, int pot){
  38. 	if(pot == 0) return 1;
  39. 	ull r = pw(base, pot/2);
  40. 	r *= r;
  41. 	if(pot % 2 == 1) r *= base;
  42. 	return r;
  43. }
  44.  
  45. ull s, x;
  46. int nbits;
  47. vi a, b, c, vx, vs, res;
  48.  
  49. bool backt(int bit, int carry){
  50. 	if(bit >= nbits) return true;
  51.  
  52. 	bool sol = false;
  53. 	if(vx[bit] == 0){
  54. 		if(vs[bit] != carry) return false;
  55. 		sol |= backt(bit + 1, 0);
  56. 		sol |= backt(bit + 1, 1);
  57. 	}
  58.  
  59. 	if(vx[bit] == 1 && vs[bit] != carry){
  60. 		sol |= backt(bit + 1, carry);
  61. 	}
  62. 	return sol;
  63. }
  64.  
  65. int main(){
  66. 	cin >> s >> x;
  67. 	nbits = hmb(s) + 1;
  68. 	int nbx = hmb(x) + 1;
  69. 	int h1x = hm1(x);
  70. 	a.assign(nbits, 0);
  71. 	b.assign(nbits, 0);
  72. 	c.assign(nbits, 0);
  73. 	res.assign(nbits, 0);
  74. 	ull ts = s;
  75. 	for(int i = 0; i < nbits; i++){
  76. 		vs.push_back(s & 1);
  77. 		s >>= 1;
  78. 	}
  79.  
  80. 	ull tx = x;
  81. 	for(int i = 0; i < nbx; i++){
  82. 		vx.push_back(x & 1);
  83. 		x >>= 1;
  84. 	}
  85.  
  86. 	bool r = backt(0,0);
  87. 	ull val = pw(2,h1x);
  88. 	if(ts == tx) val -= 2;
  89. 	if(r) cout << val << endl;
  90. 	else cout << 0 << endl;
  91. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
9 5
stdout
copy 
4
https://ideone.com/csKtVP
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!