Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 13th, 2017 47 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <array>
  4. #include <assert.h>
  5.  
  6. using namespace std;
  7.  
  8. void SiftDown( int* arr, int n, int i )
  9. {
  10.     int left = 2 * i + 1;
  11.     int right = 2 * i + 2;
  12.     int largest = i;
  13.     if( left < n && arr[left] > arr[i] )
  14.         largest = left;
  15.     if( right < n && arr[right] > arr[largest] )
  16.         largest = right;
  17.     if( largest != i ) {
  18.         std::swap( arr[i], arr[largest] );
  19.         SiftDown( arr, n, largest );
  20.     }
  21. }
  22.  
  23. void BuildHeap( int* arr, int n )
  24. {
  25.     for( int i = n / 2 - 1; i >= 0; --i ) {
  26.         SiftDown( arr, n, i );
  27.     }
  28. }
  29.  
  30. void SiftUp( int* arr, int index )
  31. {
  32.     while( index > 0 ) {
  33.         int parent = ( index - 1 ) / 2;
  34.         if( arr[index] <= arr[parent] )
  35.             return;
  36.         std::swap( arr[index], arr[parent] );
  37.         index = parent;
  38.     }
  39. }
  40.  
  41. void Add( int* arr, int n, int element )
  42. {
  43.     arr[n] = element;
  44.     if ( n == 0 )
  45.         return;
  46.     SiftUp( arr, n - 1 );
  47. }
  48.  
  49. int ExtractMax( int* arr, int n )
  50. {
  51.     int result = arr[0];
  52.     arr[0] = arr[n];
  53.     arr[n] = 0;
  54.     if( n != 0 ) {
  55.         SiftDown( arr, n, 0 );
  56.     }
  57.     return result;
  58. }
  59.  
  60. void print( int* a, int n )
  61. {
  62.     for(int i = 0; i < n; i++)
  63.         cout << a[i] << ' ';
  64.     cout << endl;
  65. }
  66.  
  67.  
  68. int main ()
  69. {
  70.     int n, k, res = 0, r, sum;
  71.     cin >> n;
  72.     if ( n == 0 )
  73.     {
  74.         cout << 0;
  75.         return 0;
  76.     }
  77.     int* a = new int[n];
  78.     for(int i = 0; i < n; i++)
  79.         cin >> a[i];
  80.     cin >> k;
  81.     int* b = new int[k];
  82.     for ( int i = 0; i < k; i++ )
  83.         b[i] = 0;
  84.     BuildHeap( a, n );
  85.     while( true )
  86.     {
  87.         sum = 0;
  88.         r = 0;
  89.         while( true )
  90.         {
  91.             int d = ExtractMax( a, n - 1 );
  92.             n--;
  93.             if( d == 0 )
  94.             {
  95.                 n++;
  96.                 break;
  97.             }
  98.             if( sum + d <= k )
  99.             {
  100.                 sum += d;
  101.                 b[r++] = d/2;
  102.             }
  103.             else
  104.             {
  105.                 Add( a, n, d );
  106.                 n++;
  107.                 break;
  108.             }
  109.         };
  110.         if ( sum != 0 )
  111.             res++;
  112.         for( int i = 0; i < r; i++ )
  113.         {
  114.             Add( a, n, b[i] );
  115.             if ( b[i] != 0 )
  116.                 n++;
  117.         };
  118.         if ( a[0] == 0 )
  119.             break;
  120.     }
  121.     cout << res;
  122.     delete []a;
  123.     delete []b;
  124.     return 0;
  125. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top