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
#include <cstdio>
#include <vector>
#include <algorithm>
#include "message.h"
#include "skup.h"
#define lld long long int
#define MAXSEND 1500000

using namespace std;

int myId, nodes;
int numCom;

// number of ints already sent by this instance
int toSend = 0;
char isBroken[100]; // if one is broken we won't receive from this guy

vector<int> data[100]; 
char hasData[100][100]; // [a][b] = "a" has data of companies in "b"
vector<int> result;

// kinda random permutation from 0 to 99
vector<int> p, rp; // rp is reversed permutation
const int perm[100] = {65,18,73,85,79,10,32,24,46,93,41,98,47,9,82,27,15,38,20,0,63,34,11,76,48,
                       29,51,77,35,55,28,54,12,56,2,59,70,69,53,23,49,7,78,21,75,14,42,33,67,88,
                       17,39,16,86,74,61,22,83,31,57,8,92,91,45,25,66,62,64,37,52,19,94,68,40,89,
                       72,96,3,44,6,50,36,95,26,43,99,80,58,97,60,4,30,13,81,71,1,87,90,5,84};

// this may generate message bigger that 64kiB, I don't care
void sendData(int node) {
    for (int i = 0; i < nodes; i++) if (toSend < MAXSEND) {
        if (hasData[myId][i] && !hasData[node][i]) {
            PutInt(node, i + 1);
            PutInt(node, data[i].size());
            for (int j = 0; j < data[i].size(); j++) {
                PutInt(node, data[i][j]);
            }
            hasData[node][i] = 1;
            toSend += data[i].size() + 2;
        }
    }   

    toSend++;
    PutInt(node, -1); // using -1 for end of message, 0 obviously means the link is broken
    Send(node);
}


void receiveData(int node) {
    if (isBroken[node]) return;
    Receive(node);
    int who, count, value;
    who = GetInt(node);
    while (who > 0) {
        who--;
        count = GetInt(node);
        hasData[node][who] = 1;
        for (int i = 0; i < count; i++) {
            value = GetInt(node);
            if (!hasData[myId][who]) {
                data[who].push_back(value);
            }
        }
        hasData[myId][who] = 1;
        who = GetInt(node);
    }
    if (who == 0) {
        isBroken[node] = 1;
    }
}


// not caring about working or not connections, just not sending same stuff twice
int main() {
    myId = MyNodeId();
    nodes = NumberOfNodes();
    numCom = NumberOfCompanies();

    for (int i = 0; i < numCom; i++) {
        data[myId].push_back(GetShareCost(i));
    }
    
    // getting random permutation of as many nodes as needed
    for (int i = 0; i < 100; i++) {
        if (perm[i] < nodes) {
            p.push_back(perm[i]);
        }
    }
    rp.resize(nodes);
    for (int i = 0; i < nodes; i++) {
        hasData[i][i] = 1;
        rp[p[i]] = i;
    }


    int bigRounds = min(1200 / nodes, nodes);
    while (bigRounds--) {
        for (int i = 0; i < nodes; i++) { // number of small round            
            int toNode   = p[(myId + i) % nodes];
            int fromNode = (rp[myId] - i + nodes) % nodes;
            if (toNode != myId) {
                sendData(toNode);
            }
            if (fromNode != myId) {
                receiveData(fromNode);
            }
        }
    }

    // Dodać wyznaczanie kto ma wypisać wynik


    vector<int> dataCount(nodes); 
    for (int i = 0; i < nodes; i++) for (int j = 0; j < nodes; j++) {
        if (hasData[i][j]) dataCount[j]++;
    }
    int whoWins = nodes;
    for (int i = 0; i < nodes; i++) {
        if (dataCount[i] == nodes) {
            whoWins = min(whoWins, i);
        }
    }

    if (myId == whoWins) {
        // yay
        for (int i = 0; i < nodes; i++) {
            for (int j = 0; j < data[i].size(); j++) {
                result.push_back(data[i][j]);
            }
        }
        sort(result.begin(), result.end());
        lld RESULT = 0;
        int j = result.size();
        for (int i = 0; i < result.size(); i++) {
            RESULT += (lld) j * result[i];
            j--;
        }
        if (myId == 0)
            printf("%lld\n", RESULT);
    }
    
    return 0;
}