fork download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4. #include<map>
  5. #include<algorithm>
  6. #include<queue>
  7. #include<fstream>
  8. #include<bitset>
  9. using namespace std;
  10.  
  11. int n;
  12. long long total;
  13. vector<vector<int> > sums;
  14.  
  15. bool works(int a, int b)
  16. {
  17. 	bitset<32> bit(0);
  18. 	for (int i = 0; i < 32; i++)
  19. 	{
  20. 		int x;
  21. 		if (a != 0)
  22. 			x = sums[b][i] - sums[a - 1][i];
  23. 		else
  24. 			x = sums[b][i];
  25.  
  26. 		if (x > 0)
  27. 			bit[i] = 1;
  28. 	}
  29.  
  30. 	return (total == bit.to_ulong());
  31. }
  32.  
  33. int solve(int i)
  34. {
  35. 	int ans = n - 1;
  36. 	int a = 0;
  37. 	int b = n-1;
  38. 	while (a <= b)
  39. 	{
  40. 		int mid = (a + b) / 2;
  41. 		if (works(i, mid))
  42. 		{
  43. 			ans = min(ans, mid);
  44. 			b = mid - 1;
  45. 		}
  46. 		else
  47. 			a = mid + 1;
  48. 	}
  49.  
  50. 	return ans;
  51. }
  52.  
  53. int main()
  54. {
  55. 	cin >> n;
  56. 	vector<long long> v(n);
  57. 	total = 0;
  58. 	for (int i = 0; i < n; i++)
  59. 	{
  60. 		cin >> v[i];
  61. 		total |= v[i];
  62. 	}
  63.  
  64. 	if (total == 0)
  65. 	{
  66. 		cout << 1 << endl;
  67. 		return 0;
  68. 	}
  69.  
  70. 	sums.assign(n,vector<int>(32,0));
  71. 	for (int i = 0; i < n; i++)
  72. 	{
  73. 		if (i != 0)
  74. 			sums[i] = sums[i - 1];
  75. 		bitset<32> b(v[i]);
  76.  
  77. 		for (int j = 0; j < 32; j++)
  78. 			if (b[j] == 1)
  79. 				sums[i][j]++;
  80. 	}
  81.  
  82. 	int ans = n;
  83. 	for (int i = 0; i < n; i++)
  84. 	{
  85. 		int j = solve(i);
  86. 		if(works(i,j))
  87. 			ans = min(ans, j - i + 1);
  88. 	}
  89.  
  90. 	cout << ans << endl;
  91.  
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 4420KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/5PIOCe
language:
C++14 (gcc 8.3)
created:
4 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!