fork download
copy 
  1. #include <iostream>
  2. #include <numeric>
  3. #include <vector>
  4. using namespace std;
  5. vector<int> arr;
  6. vector<int> arr1;
  7. vector<int> arr2;
  8. int qq = 0;
  9. bool checkSum(int sumLeft[], int k)
  10. {
  11. 	int r = true;
  12. 	for (int i = 0; i < k; i++)
  13. 	{
  14. 		if (sumLeft[i] != 0)
  15. 			r = false;
  16. 	}
  17. 	return r;
  18. }
  19. bool subsetSum(int S[], int n, int sumLeft[], int A[], int k)
  20. {
  21. 	if (checkSum(sumLeft, k))
  22. 		return true;
  23. 	if (n < 0)
  24. 		return false;
  25. 	bool res = false;
  26. 	for (int i = 0; i < k; i++)
  27. 	{
  28. 		if (!res && (sumLeft[i] - S[n]) >= 0)
  29. 		{
  30. 			A[n] = i + 1;
  31. 			sumLeft[i] = sumLeft[i] - S[n];
  32. 			res = subsetSum(S, n - 1, sumLeft, A, k);
  33. 			sumLeft[i] = sumLeft[i] + S[n];
  34. 		}
  35. 	}
  36. 	return res;
  37. }
  38. void partition(int S[], int n, int k)
  39. {
  40. 	if (n < k)
  41. 	{
  42. 		std::cout << -1;
  43. 		qq = 1;
  44. 		return;
  45. 	}
  46. 	int sum = std::accumulate(S, S + n, 0);
  47.  	int A[n], sumLeft[k];
  48. 	for (int i = 0; i < k; i++)
  49. 		sumLeft[i] = sum/k;
  50. 	bool res = !(sum % k) && subsetSum(S, n - 1, sumLeft, A, k);
  51. 	if (!res)
  52. 	{
  53. 		std::cout << -1;
  54. 		qq = 1;
  55. 		return;
  56. 	}
  57. 	int q = 0,q1 = 0,q2 = 0,z;
  58. 	for (int i = 0; i < k; i++)
  59. 	{
  60. 		for (int j = 0; j < n; j++) {
  61. 			if (A[j] == i+1 && i==0){
  62. 				arr.push_back(S[j]);
  63. 			}
  64. 			if (A[j] == i+1 && i==1){
  65. 				arr1.push_back(S[j]);
  66. 			}
  67. 			if (A[j] == i+1 && i==2){
  68. 				arr2.push_back(S[j]);
  69. 			}
  70. 		}
  71. 	}
  72. }
  73. int main()
  74. {
  75.     int n;
  76. 	cin >> n;
  77. 	int a[n];
  78.     for (int i=0;i<n;i++){
  79.         cin>>a[i];
  80.     }
  81. 	partition(a, n, 3);
  82. 	if (qq != 1) {
  83. 		cout << arr.size() << " " << arr1.size() << " " << arr2.size() << endl;
  84. 		for (int i = 0; i <= arr.size()-1; i++) {
  85. 			cout << arr[i] << " ";
  86. 		}
  87. 		cout << endl;
  88. 		for (int i = 0; i <= arr1.size()-1; i++) {
  89. 			cout << arr1[i] << " ";
  90. 		}
  91. 		cout << endl;
  92. 		for (int i = 0; i <= arr2.size()-1; i++) {
  93. 			cout << arr2[i] << " ";
  94. 		}
  95. 	}
  96. 	return 0;
  97. }
  98.  
  99.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/dANhsS
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!