pastebin

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