1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include "message.h"
#include "krazki.h"

#include <vector>
#include <iostream>

using namespace std;
typedef long long int LL;

LL depth;
LL disks;
int instances ;

 
LL findBlocker(LL upper, LL lower)                           
{     
    if (depth < disks) return 0;           
    if (lower == 0) return 0;		   //    -- upper (1)  inclusive	
    LL h = lower-upper+1;                  //   ----
    vector<LL> pipeDiamater(h);            //    -- lower (3)  inclusive
					   //    --
					   //     - total depth (5)
    pipeDiamater[0]=HoleDiameter(upper);                                 

    for(LL i=1; i < h; i++)
    {
	pipeDiamater[i]=HoleDiameter(i+upper);
        if (pipeDiamater[i] > pipeDiamater[i-1]) pipeDiamater[i]=pipeDiamater[i-1];  // lejek   \   /   pipeline[0]
    }                                                                                //          \ /    pipeline[1]
    
    LL filled = 0;
    LL minSize = pipeDiamater[h-1];
    LL shift = 0;
    LL stacked = 0;
    
    for(LL i=1; i<=disks; i++)
    {
	LL size = DiscDiameter(i);
	
	
	//cout << "disk: " << i << " size: " << size << " " << shift << " " << stacked << " min size: " <<  minSize << endl;
	
	if (size <= minSize)		// przechodzi
	{  
	    if (stacked)
		minSize = pipeDiamater[--stacked-1];
	    continue;   
	}
        else				// nie przechodzi - szukam, gdzie sie zatrzyma
        {
	    LL blockIndex = (stacked != 0 ? stacked : h-1);
            while ((blockIndex>=0) && (size > pipeDiamater[blockIndex])) blockIndex-- ;
            
	    shift = depth - upper - blockIndex - i + 1;   // depth - upper <- tyle powinno wejsc dyskow, weszlo juz i, teraz zacielo sie na wysokosci blockIndex
	    
	    if ( blockIndex > 0 )
	    {
		minSize = pipeDiamater[blockIndex-1];			// pierwsze wolne miejsce
		stacked = blockIndex;					// miejsce gdzie zablokowal sie ostatni krazek
	    }
        }
        
        if (stacked == 1) break;
        if (shift >= depth - i + 1)  break;  // wystaje gora
        if (shift + upper + i - 2 >= depth) break;   // opieramy sie o dno
    }

    return shift;       
}

int main() {
  
    instances = NumberOfNodes();
    depth = PipeHeight();
    disks = NumberOfDiscs();
    LL h = depth/(instances - 1);

    int myinstance = MyNodeId();
    LL lower = myinstance * h + 1;
    LL upper = ( myinstance + 1 ) * h;

    if (myinstance == instances - 2) upper = depth;
    if (myinstance != instances - 1)
    {
	//cout << myinstance << " " << lower << " " << upper << endl; 
	PutLL(instances - 1, findBlocker(lower, upper));
        Send(instances - 1);
        return 0;
     }
     LL shift = 0;
     for (int i=0; i<instances - 1; i++)
     {
	Receive(i);
        LL s = GetLL(i);
	//cout << i << "r " << s << endl;
        if (s > shift) shift = s;
     }
     
     shift = depth - disks - shift + 1;
     if (shift < 0) shift = 0;
     cout << shift << endl;

     return 0;
}