fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. // Can be used for GCD, LCM, Maximum, Minimum queries, OR this code is for Range Minimum Query AKA RMQ
  7. struct sparseTable
  8. {
  9. 	int size, LOG;
  10. 	vector<vector<ll>> m;
  11.  
  12. 	ll merge(const ll &a, const ll &b)
  13. 	{
  14. 		return gcd(a, b);
  15. 	}
  16.  
  17. 	void build(const vector<ll> &arr)
  18. 	{
  19. 		int N = arr.size();
  20. 		for (int i{}; i < N; i++)
  21. 			m[i][0] = arr[i];
  22.  
  23. 		for (int k = 1; k < LOG; k++)
  24. 		{
  25. 			for (int i{}; i + (1 << k) - 1 < N; i++)
  26. 				m[i][k] = merge(m[i][k - 1], m[i + (1 << (k - 1))][k - 1]);
  27. 		}
  28. 	}
  29.  
  30. 	sparseTable(const vector<ll> &arr, int lg)
  31. 	{
  32. 		int n = arr.size();
  33. 		LOG = lg;
  34. 		m.resize(n, vector<ll>(LOG, 0));
  35. 		build(arr);
  36. 	}
  37.  
  38. 	ll query(int L, int R) // 0-based
  39. 	{
  40. 		int len = R - L + 1;
  41. 		int k = 31 - __builtin_clz(len);
  42. 		return merge(m[L][k], m[R - (1 << k) + 1][k]);
  43. 	}
  44. };
  45.  
  46. int main()
  47. {
  48. 	ios_base::sync_with_stdio(false);
  49. 	cin.tie(nullptr);
  50. #ifndef ONLINE_JUDGE
  51. 	freopen("input.txt", "r", stdin);
  52. 	freopen("Output.txt", "w", stdout);
  53. #endif //! ONLINE_JUDGE
  54. 	int t = 1;
  55. 	ll N;
  56. 	// cin >> t;
  57. 	while (t--)
  58. 	{
  59. 		cin >> N;
  60. 		vector<ll> vc(N);
  61. 		for (int i{}; i < N; i++)
  62. 			cin >> vc[i];
  63.  
  64. 		sparseTable SPT(vc, 17);
  65. 		int minLen = 0x7fffffff, L{}, R{};
  66. 		ll g{};
  67. 		while (R < N)
  68. 		{
  69. 			g = gcd(g, vc[R]); // Expand
  70. 			if (g == 1)
  71. 				minLen = min(minLen, R - L + 1);
  72.  
  73. 			while (g == 1 && L < R) // Shrink
  74. 			{
  75. 				minLen = min(minLen, R - L + 1);
  76. 				L++;
  77. 				g = SPT.query(L, R);
  78. 			}
  79. 			if (g == 1)
  80. 				minLen = min(minLen, R - L + 1);
  81. 			R++;
  82. 		}
  83. 		if (minLen != INT_MAX)
  84. 			cout << minLen;
  85. 		else
  86. 			cout << -1;
  87. 	}
  88. 	return 0;
  89. }
Success #stdin #stdout #stderr 0.25s 40548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/Fa1i4w
language:
R (R 3.5.2)
created:
6 days 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!