fork download
copy 
  1. /******************************************************************************
  2.  
  3. Welcome to GDB Online.
  4. GDB online is an online compiler and debugger tool for C/C++.
  5. Code, Compile, Run and Debug online from anywhere in world.
  6.  
  7. *******************************************************************************/
  8. #include <iostream>
  9. #include <bits/stdc++.h>
  10. #include <boost/uuid/string_generator.hpp>
  11. #include <boost/uuid/uuid.hpp>
  12. using namespace std;
  13.  
  14. vector < vector < int > > finalVec;
  15.  
  16. void printArray(int p[], int n)
  17. {
  18. 	vector < int > vec;
  19.     for (int i = 0; i < n; i++)
  20.        vec.push_back(p[i]);
  21.     finalVec.push_back(vec);
  22.     return;
  23. }
  24.  
  25. void printAllUniqueParts(int n)
  26. {
  27.     int p[n]; // An array to store a partition
  28.     int k = 0;  // Index of last element in a partition
  29.     p[k] = n;  // Initialize first partition as number itself
  30.  
  31.     // This loop first prints current partition, then generates next
  32.     // partition. The loop stops when the current partition has all 1s
  33.     while (true)
  34.     {
  35.         // print current partition
  36.         printArray(p, k+1);
  37.  
  38.         // Generate next partition
  39.  
  40.         // Find the rightmost non-one value in p[]. Also, update the
  41.         // rem_val so that we know how much value can be accommodated
  42.         int rem_val = 0;
  43.         while (k >= 0 && p[k] == 1)
  44.         {
  45.             rem_val += p[k];
  46.             k--;
  47.         }
  48.  
  49.         // if k < 0, all the values are 1 so there are no more partitions
  50.         if (k < 0)  return;
  51.  
  52.         // Decrease the p[k] found above and adjust the rem_val
  53.         p[k]--;
  54.         rem_val++;
  55.  
  56.  
  57.         // If rem_val is more, then the sorted order is violeted.  Divide
  58.         // rem_val in differnt values of size p[k] and copy these values at
  59.         // different positions after p[k]
  60.         while (rem_val > p[k])
  61.         {
  62.             p[k+1] = p[k];
  63.             rem_val = rem_val - p[k];
  64.             k++;
  65.         }
  66.  
  67.         // Copy rem_val to next position and increment position
  68.         p[k+1] = rem_val;
  69.         k++;
  70.     }
  71. }
  72.  
  73.  
  74. int main() {
  75. 	// your code goes here
  76. 	int n; cin >> n;
  77.  
  78. 	printAllUniqueParts(n);
  79. 	cout << "size : " << finalVec.size() << endl;
  80. 	multiset < int > :: iterator it;
  81.  
  82. 	int ANS = 0;
  83. 	vector < int > ansVec;
  84. 	for (int i = 0; i < finalVec.size(); i++) {
  85. 		multiset < int > mySet;
  86.  
  87. 		vector < int > temp = finalVec[i];
  88.  
  89. 		for (int ii = 0; ii < temp.size(); ii++) {
  90. 			mySet.insert(temp[ii]);
  91. 		}
  92.  
  93. 		int t = n + 4;
  94. 		int cnt = 0;
  95. 		while (t --) {
  96. 			multiset < int > newSet;
  97. 			newSet.insert(mySet.size());
  98.  
  99. 			for (it = mySet.begin(); it != mySet.end(); it++) {
  100. 				if(*it > 1) {
  101. 					newSet.insert((*it) - 1);
  102. 				}
  103. 			}
  104.  
  105. 			if(newSet == mySet) {
  106. 				if(cnt > ANS) {
  107. 				    ANS = cnt;
  108. 				    ansVec = temp;
  109. 				}
  110. 				break;
  111. 			}
  112.  
  113. 			cnt++;
  114. 			mySet = newSet;
  115. 		}
  116. 	}
  117.  
  118. 	cout << ANS << endl;
  119. 	for (int i = 0; i < ansVec.size(); i++) cout << ansVec[i] << ' ';
  120. 	cout << endl;
  121.  
  122. 	return 0;
  123. }
  124.  
  125.  
  126.  
Success #stdin #stdout 2.34s 11252KB
comments (?)
stdin
copy 
45
stdout
copy 
size : 89134
48
38 7
https://ideone.com/TGwPRW
language:
C++14 (gcc 8.3)
created:
1 year 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!