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
#include <cstdio>

#include "krazki.h"
#include "message.h"

inline long long min(long long a, long long b) { return a < b ? a : b; }
inline long long max(long long a, long long b) { return a > b ? a : b; }

int main() {
    if (MyNodeId() != 0) {
        return 0;
    }
    
    int n = PipeHeight();
    int m = NumberOfDiscs();

    int tabMax = 30000000;
    long long cmin, mins[10];
    long long *pipe = new long long[tabMax];
    cmin = HoleDiameter(1);
    for (int i = n - 1; i > 0; --i) {
        cmin = min(cmin, HoleDiameter(n - i));
        if (i % tabMax == 0) mins[i / tabMax] = cmin;
    }
    mins[(n + tabMax - 1) / tabMax] = HoleDiameter(1);
    
    int i = 0, j = 1, load = 0;
    while (i < n && j <= m) {
        if (i % tabMax == 0) {
            int from = load * tabMax;
            int to = min(n, ++load * tabMax);
            cmin = mins[load];
            //fprintf(stderr, "loading[%d, %d)\n", from, to);
            //fprintf(stderr, "current mins[%d] = %lld\n", load, cmin);
            for (int i = to - 1; i >= from; --i) {
                cmin = min(cmin, HoleDiameter(n - i));
                pipe[i % tabMax] = cmin;
                //fprintf(stderr, "setting pipe[%d]=%lld\n", i % tabMax, cmin);
            }
        }
        
        if (pipe[i % tabMax] >= DiscDiameter(j)) {
            i++;
            j++;
        } else {
            i++;
        }
    }
    
    if (j <= m) printf("0\n");
    else {
        printf("%d\n", n - i + 1);
    }
    //fprintf(stderr, "i=%d, j=%d\n", i, j);
    
    return 0;
}