fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int countSplits(vector<int> &arr){
  5. 	int n= arr.size();
  6.  
  7. 	 vector<int> pgcd(n);
  8.       vector<int> sgcd(n);
  9.  
  10.        pgcd[0]= arr[0];
  11.            for (int i=1;i<n;i++){
  12.             pgcd[i]=__gcd(pgcd[i-1],arr[i]);
  13.         }
  14.  
  15.          sgcd[n-1]=arr[n-1];
  16.         for(int i=n-2;i>=0;i--){
  17.             sgcd[i]=__gcd(sgcd[i+1],arr[i]);
  18.         }
  19.  
  20.         int count =0;
  21.  
  22.         for(int i=0;i<n-1;i++){
  23.         	if(pgcd[i]==sgcd[i+1])
  24.         	count++;
  25.         }
  26.         return count;
  27. }
  28.  
  29. int main() {
  30. 	// your code goes here
  31. 	int n;
  32. 	cin>>n;
  33.  
  34. 	vector<int>nums(n);
  35. 	for(int i=0;i<n;i++){
  36. 		cin>>nums[i];
  37. 	}
  38.  
  39. 	vector<int> pgcd(n);
  40. 	pgcd[0]=nums[0];
  41.  
  42. 	for(int i=1;i<n;i++){
  43. 		pgcd[i]=__gcd(pgcd[i-1],nums[i]);
  44. 	}
  45.  
  46. 	vector<int> sgcd(n);
  47. 	sgcd[n-1]=nums[n-1];
  48.  
  49. 	for(int i = n-2; i>=0;i--){
  50. 		sgcd[i]=__gcd(sgcd[i+1],nums[i]);
  51. 	}
  52.  
  53. 	int ans = countSplits(nums);
  54.  
  55. 	// Find arrow position
  56. 	for (int i=0;i<n;i++){
  57. 		bool arrow = false;
  58.  
  59. 		if(i>0 && pgcd[i]!=pgcd[i-1])
  60. 		arrow = true;
  61.  
  62. 		if(i<n-1 && sgcd[i]!=sgcd[i+1])
  63. 		arrow = true;
  64.  
  65. 		if(arrow==true){
  66. 			vector<int>temp;
  67.  
  68. 			for( int j=0;j<n;j++){
  69. 				if(j!=i)
  70. 				temp.push_back(nums[j]);
  71. 			}
  72. 			ans= max(ans, countSplits(temp));
  73. 		}
  74.  
  75. 	}
  76. 	cout<<ans<<endl;
  77.  
  78. 	return 0;
  79. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
4
10 30 15 10
stdout
copy 
2
https://ideone.com/qnzTSi
language:
C++ (gcc 8.3)
created:
5 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!