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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
//  budowanie za pomocą polecenia:
/// rpa build --source=kra.cpp --library krazki.cpp
//
//  uruchamianie
/// rpa run --executable=./kra --nodes=100 --output=all
//
//  komplet:
/// rpa build --source=kra.cpp --library krazki.cpp && rpa run --executable=./kra --nodes=100 --output=all < kra0.in

#include<vector>
#include<iostream>
#include<stdint.h>
#include<limits.h>

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

using namespace std;

//#define DEBUG

#ifdef DEBUG
#define ifdebug if(true)
#else
#define ifdebug if(false)
#endif


/// Struktura opisująca fragment pseudo stożka, czyli lejeka, który się zmniejsza, ale niekoniecznie regularnie.
struct ConeInfo {
    int64_t diameter;       /// szerokość
    int32_t height;         /// jak długo jest ta szerokość
};

vector<ConeInfo> cone;      /// wektor z fragmentami stożka, czyli stożek
int64_t maxDiameter=LONG_MAX;   /// limit średnicy (dla drugiego etapu)
int32_t height;             /// wysokość danego fragmetnu stożka

/// Metoda budująca opis stożka dla zadanego fragmentu
void buildCone(int32_t from, int32_t to) {
    ConeInfo c;
    c.diameter=HoleDiameter(from+1);
    c.height=1;
    for(int32_t i=from+1;i<to;++i) {
        int64_t d=HoleDiameter(i+1);
        if(d<c.diameter){ // jeżeli następuje zwężenie,
            cone.push_back(c);  // to dotychczasowy fragment odkładamy
            c.diameter=d;   // inicjujemy nowy fragment, który ma nową szerokość
            c.height=1;
        } else c.height++;  // jeżeli jest taki sam lub większy, to po prostu dany fragment wydłużamy
    }
    cone.push_back(c);      // oraz ostatni element dodajemy
    height=to-from;         // ustawiamy wysokość
}

/// Funkcja zapełniająca stożek dyskami zaczynąjąc od zadanego stożka (licząc od 1, nie od 0)
/// Funkcja zwraca nr dysku, który się już nie zmieścił lub 0, gdy wszystkie się zmieściły
/// Funkcja aktualizuje wysokość stożka
int32_t fillCone(int32_t from) {
    int32_t discs=NumberOfDiscs();
    int pos=cone.size();  /// pozycja w stożku na której jesteśmy
    ConeInfo c;
    c.diameter=-1;
    c.height=0;

    int64_t d=DiscDiameter(from);   /// rozmiar krążka, ktory badamy
    for(;;) {
        ifdebug cerr<<"Process disc "<<from<<" (@"<<d<<") with cone part "<<pos<<" (d="<<c.diameter<<", h="<<c.height<<")"<<endl;

        if(c.diameter>=d && c.height>0) {     // to dysk się mieści i jest miejsce w tym fragmencie
            --c.height; --height;   // zmiejszamy ilość miejsca w danym fragmencie, jak i całkowitą wysokość
            ++from;          // jeżeli się zmieścił, to przechodzimy do następnego do rospatrzenia
            if(from>discs) return 0;  // nie ma już dysków koniec
            d=DiscDiameter(from);       // bierzemy kolejny krązek, który badamy
        } else {    // jeżeli dysk jest za duży lub skończyło się miejsce w danym fragmencie stożka
            --pos;
            height-=c.height;           // zmniejszamy wysokość o to co nie zostało wykorzystane
            if(pos<0) return from;    // jeżeli nie ma już dostępnych fragmentów stożka, to ten element się już nie zmieścił
            c=cone[pos];        // przechodzimy do następnego fragmentu stożka
            if(c.diameter>maxDiameter) c.diameter=maxDiameter;  // korygujemy rozmiar
        }
    }
}

int main(int argc, char** argv) {
    const int64_t h=PipeHeight();
    const int myId=MyNodeId();
    const int nodes=NumberOfNodes();

    //ifdebug cerr<<"Started node: "<<myId<<"/"<<nodes<<endl;

    //if(h<10) {  // TODO: Na testy
    if(h<100000) {  // jeżeli zadań jest mało to liczy na jednym węźle
        if(myId!=0) return 0;   // pozostałe nic nie robią, tylko pierwszy rozwiązuje proste zagadnienia

        ifdebug cerr<<"Simple task mode"<<endl;

        buildCone(0, h);        // budujemy stożek z całości
        ifdebug {
            cerr<<"Build cone: Cone size: "<<cone.size()<<" last part diameter: "<<cone[cone.size()-1].diameter<<endl;
            for(int i=0;i<cone.size();++i) {
                cerr<<"\t"<<(i+1)<<": D="<<cone[i].diameter<<", H="<<cone[i].height<<endl;
            }
        }
        int32_t res=fillCone(1);    // wypełniamy stożek danymi
        ifdebug cerr<<"Processed with result: "<<res<<" and height: "<<height<<endl;
        if(res==0) cout<<(height+1)<<endl;  // jeżeli wszystkie stożki się zmieścily, to zwracamy położenie ostatniego stożka, czyli height+1
        else cout<<"0"<<endl;   // funkcja fillCone, zwraca stożek, który się nie zmieścił, więc na potrzeby zadania to jest 0
        return 0;
    }

    // etap 1 - podział zadania

    int32_t from=(h*(int64_t)myId)/nodes;       /// zakres od
    int32_t to=(h*(int64_t)(myId+1))/nodes;               /// zakres do

    ifdebug cerr<<"["<<myId<<"] Processing part: "<<from<<"-"<<to<<endl;

    buildCone(from, to);            // budujemy stożek dla swojej częsci
    ifdebug cerr<<"["<<myId<<"] Processed data; Cone size: "<<cone.size()<<" last part diameter: "<<cone[cone.size()-1].diameter<<endl;

    if(myId>0) {  // jeżeli nie jesteśmy pierwszym komputerem, to oczekujemy informacje o stożku od poprzedniego komputera
        Receive(myId-1);  // oczekujemy na wiadomość o poprzednika
        maxDiameter=GetLL(myId-1);  // i ją odbieramy - jest to maksymalna szerokość stożka
        ifdebug cerr<<"["<<myId<<"] got maxDiameter from predecessor: "<<maxDiameter<<endl;
    }

    if(myId+1<nodes) {  // jeżeli nie jesteśmy komputerem, zajmującym się ostatnim fragmentem, to wysyłamy informacje o ostatnim fragmentcie; maksymalnej szerokości
        int64_t lastDiameter=cone[cone.size()-1].diameter;
        if(lastDiameter>maxDiameter) lastDiameter=maxDiameter;      // korygujemy
        PutLL(myId+1, lastDiameter);
        Send(myId+1);
    }

    int32_t start;
    int32_t lastHeight;
    if(myId+1<nodes) {   // jeżeli nie jesteśmy komputerem, zajmującym się ostatnim fragmentem, to oczekujemy na informacje o wyliczeniach od poprzednika
        Receive(myId+1);    // oczekujemy na dane od następnika
        start=GetInt(myId+1);       // dysk od którego nalezy zacząć działanie
        lastHeight=GetInt(myId+1);  // wysokość wstawienia ostatniego dysku
        ifdebug cerr<<"["<<myId<<"] received data from successor; start: "<<start<<" lastHeight: "<<lastHeight<<endl;
    } else {
        start=1;    // jeżeli jesteśmy ostatnim komputerem, to rozpoczynamy obliczanie z pierwszym dyskiem
        lastHeight=0;
    }

    int32_t res;

    if(start>0) {   // jeżeli jeszcze są jakieś dyski, to pracujemy
		ifdebug cerr<<"["<<myId<<"] processing part ("<<from<<"-"<<to<<") from disk "<<start<<endl;
        res=fillCone(start);
        ifdebug cerr<<"["<<myId<<"] processed own part ("<<from<<"-"<<to<<") from disk "<<start<<" with result: "<<res<<" and height: "<<height<<endl;
        if(res==0) {    // jeżeli zmieściły się wszystkie dyski, to pozycja ostatniego dysku
            lastHeight=(height+1)+from;
        }
    } else res=0;

    if(myId>0) {
        // przesyłamy wyniki do poprzednika
        PutInt(myId-1, res);
        PutInt(myId-1, lastHeight);
        Send(myId-1);
    } else {    // jeżeli jesteśmy pierwszym komputerem, to zwracamy wynik
        if(res==0) cout<<lastHeight<<endl;
        else cout<<"0"<<endl;
    }

    return 0;
}