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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include "krazki.h"
#include "message.h"
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

void node_calc_mm( ll id, ll nn ) {
    ll n,b,e,r;

    n = PipeHeight();
    b = (id*n)/nn+1;
    e = ((id+1)*n)/nn+1;
    r = 1e18+(ll)18;
    for ( ll i=b; i<e; i++ )
        r = min( r, HoleDiameter(i) );
    PutLL( 0, r );
    
    n = NumberOfDiscs();
    b = (id*n)/nn+1;
    e = ((id+1)*n)/nn+1;
    r = 0;
    for ( ll i=b; i<e; i++ )
        r = max( r, DiscDiameter(i) );
    PutLL( 0, r );
}

ll A[ 2000006 ];
ll node_proc_data( ll a1, ll a2, ll nn ) {
    ll n1,b1,e1,n2,b2,e2;

    //printf("%lld %lld\n",a1,a2);
    n1 = PipeHeight();
    b1 = (a1*n1)/nn+1;
    e1 = ((a1+1)*n1)/nn+1;
    //b1=3; e1=4;
    //printf("%lld %lld\n",b1,e1);
 
    n2 = NumberOfDiscs();
    b2 = (a2*n2)/nn+1;
    e2 = ((a2+1)*n2)/nn+1; 
    //b2=2; e2=3;
    //printf("     %lld %lld\n",b2,e2);

    ll mm = 1e18+(ll)18;
    for ( ll i=b1; i<e1; i++ ) {
        ll v = HoleDiameter( i );
        mm = min( mm, v );
        A[i-b1] = mm;
    }
    //printf("ooooo   "); for ( ll i=b1; i<e1; i++ ) printf("%d ",A[i-b1]); printf("\n");

    ll a = e1-b1-1;
    ll r = 0;
    for ( ll i=b2; i<e2; i++ ) {
        ll v = DiscDiameter( i );
        //printf("uuuu     %lld %lld\n",a,i);
        while ( a>=0 && v>A[a] ) a--;
        if ( v>mm ) {
            //printf("uuuu     %lld %lld\n",a+b1,i);
            r = max( r, n1-(a+b1)+(n2-i) );
        }
    }

    //printf("rrrrrrrrrrrrr %lld\n",r);
    return r;
}

ll B[ 5003 ];
void node_sum_res1( ll nn, ll nmul  ) {
    for ( ll _i=0; _i<nn; _i++ ) {
        ll _inst = Receive( -1 );
        for ( ll id=_inst*nmul; id<_inst*nmul+nmul; id++ ) {
            A[id] = GetLL( _inst );
            B[id] = GetLL( _inst );
        }
    }
    nn *= nmul;
    ll aa=1e18+(ll)18,bb=0;
    for ( ll i=0; i<nn; i++ ) {
        aa=min( aa, A[i] );
        //bb=max( bb, B[i] );
        A[i]=aa; //B[i]=bb;
    }
    //for ( ll i=0; i<nn; i++ ) printf("%lld ",A[i]); printf("\n");
    //for ( ll i=0; i<nn; i++ ) printf("%lld ",B[i]); printf("\n");
    aa=0;
    aa = nn-1;
    ll cc = 0;
    for ( ll i=0; i<nn; i++ ) {
        while ( aa>0 && B[i]>A[aa-1] ) aa--;
        //printf("oooooo %lld %lld\n",aa,i);
        if ( A[aa]<B[i] ) {
            PutLL( i/nmul, aa );
            PutLL( i/nmul, i );
        }
        if (!(i%nmul)) {
            PutLL( i/nmul, -1 );
            Send( i/nmul );
        }
    }
}

void node_sum_res2( ll nn, ll nmul  ) {
    ll r = NumberOfDiscs()-1;
    for ( ll _i=0; _i<nn; _i++ ) {
        ll _inst = Receive( -1 );
        r = max( r, GetLL(_inst) );
    }
    printf("%lld\n",max((ll)0,PipeHeight()-r));
}

int main() {
    ll n = max( PipeHeight(), NumberOfDiscs() );

    ll id = MyNodeId();
    ll nn = NumberOfNodes();

    ll nmul=1;
    if ( n/nn > 1e6 ) nmul = (n*2)/nn/1e6;

    for ( ll i=0; i<nmul; i++ ) {
        node_calc_mm( id*nmul+i, nn*nmul );
    }
    Send(0);

    if ( !id ) node_sum_res1( nn, nmul );

    Receive( 0 );
    ll r = 0;
    ll a = 0,b = 0;
    while ( 1 ) {
        a = GetLL( 0 );
        if ( a < 0 ) break;
        b = GetLL( 0 );
        r = max( r, node_proc_data( a, b, nn*nmul ) );
    }
    PutLL( 0, r );
    Send(0);

    if ( !id ) node_sum_res2( nn, nmul );

    return 0;
}