#include <iostream>
#include <vector>
#include <cmath> 
#include <mpi.h>

void gaussianElimination(vector<vector<double> >& A, vector<double>& b, int rank, int size) {
    int n = A.size();
    int rows_per_process = n / size;

    for (int i = 0; i < n; ++i) {
        int maxRow;
        double maxVal = 0.0;
        for (int k = i + rank * rows_per_process; k < n; k += size * rows_per_process) {
            if (fabs(A[k][i]) > maxVal) {
                maxRow = k;
                maxVal = fabs(A[k][i]);
            }
        }
        MPI_Allreduce(MPI_IN_PLACE, &maxRow, 1, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
        if (i % size == rank) {
            swap(A[i], A[maxRow]);
            swap(b[i], b[maxRow]);
        }
        MPI_Bcast(&A[i][0], n, MPI_DOUBLE, i % size, MPI_COMM_WORLD);
        MPI_Bcast(&b[i], 1, MPI_DOUBLE, i % size, MPI_COMM_WORLD);

        for (int k = i + 1 + rank * rows_per_process; k < n; k += size * rows_per_process) {
            double factor = -A[k][i] / A[i][i];
            for (int j = i; j < n; ++j) {
                A[k][j] += factor * A[i][j];
            }
            b[k] += factor * b[i];
        }
    }

    vector<vector<double> > global_A(n, vector<double>(n));
    vector<double> global_b(n);
    MPI_Gather(&A[0][0], rows_per_process * n, MPI_DOUBLE, &global_A[0][0], rows_per_process * n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
    MPI_Gather(&b[0], rows_per_process, MPI_DOUBLE, &global_b[0], rows_per_process, MPI_DOUBLE, 0, MPI_COMM_WORLD);

    if (rank == 0) {
        vector<double> x(n);
        for (int i = n - 1; i >= 0; --i) {
            x[i] = global_b[i] / global_A[i][i];
            for (int k = i - 1; k >= 0; --k) {
                global_b[k] -= global_A[k][i] * x[i];
            }
        }

        cout << "Solution:\n";
        for (int i = 0; i < n; ++i) {
            cout << "x[" << i << "] = " << x[i] << endl;
        }
    }
}

int main(int argc, char** argv) {
    MPI_Init(&argc, &argv);

    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    vector<vector<double> > A(3, vector<double>(3));
    A[0][0] = 2; A[0][1] = 1; A[0][2] = -1;
    A[1][0] = -3; A[1][1] = -1; A[1][2] = 2;
    A[2][0] = -2; A[2][1] = 1; A[2][2] = 2;

    vector<double> b(3);
    b[0] = 8; b[1] = -11; b[2] = -3;

    gaussianElimination(A, b, rank, size);

    MPI_Finalize();

    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y21hdGg+IAojaW5jbHVkZSA8bXBpLmg+Cgp2b2lkIGdhdXNzaWFuRWxpbWluYXRpb24odmVjdG9yPHZlY3Rvcjxkb3VibGU+ID4mIEEsIHZlY3Rvcjxkb3VibGU+JiBiLCBpbnQgcmFuaywgaW50IHNpemUpIHsKICAgIGludCBuID0gQS5zaXplKCk7CiAgICBpbnQgcm93c19wZXJfcHJvY2VzcyA9IG4gLyBzaXplOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgaW50IG1heFJvdzsKICAgICAgICBkb3VibGUgbWF4VmFsID0gMC4wOwogICAgICAgIGZvciAoaW50IGsgPSBpICsgcmFuayAqIHJvd3NfcGVyX3Byb2Nlc3M7IGsgPCBuOyBrICs9IHNpemUgKiByb3dzX3Blcl9wcm9jZXNzKSB7CiAgICAgICAgICAgIGlmIChmYWJzKEFba11baV0pID4gbWF4VmFsKSB7CiAgICAgICAgICAgICAgICBtYXhSb3cgPSBrOwogICAgICAgICAgICAgICAgbWF4VmFsID0gZmFicyhBW2tdW2ldKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBNUElfQWxscmVkdWNlKE1QSV9JTl9QTEFDRSwgJm1heFJvdywgMSwgTVBJX0lOVCwgTVBJX01BWCwgTVBJX0NPTU1fV09STEQpOwogICAgICAgIGlmIChpICUgc2l6ZSA9PSByYW5rKSB7CiAgICAgICAgICAgIHN3YXAoQVtpXSwgQVttYXhSb3ddKTsKICAgICAgICAgICAgc3dhcChiW2ldLCBiW21heFJvd10pOwogICAgICAgIH0KICAgICAgICBNUElfQmNhc3QoJkFbaV1bMF0sIG4sIE1QSV9ET1VCTEUsIGkgJSBzaXplLCBNUElfQ09NTV9XT1JMRCk7CiAgICAgICAgTVBJX0JjYXN0KCZiW2ldLCAxLCBNUElfRE9VQkxFLCBpICUgc2l6ZSwgTVBJX0NPTU1fV09STEQpOwoKICAgICAgICBmb3IgKGludCBrID0gaSArIDEgKyByYW5rICogcm93c19wZXJfcHJvY2VzczsgayA8IG47IGsgKz0gc2l6ZSAqIHJvd3NfcGVyX3Byb2Nlc3MpIHsKICAgICAgICAgICAgZG91YmxlIGZhY3RvciA9IC1BW2tdW2ldIC8gQVtpXVtpXTsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IGk7IGogPCBuOyArK2opIHsKICAgICAgICAgICAgICAgIEFba11bal0gKz0gZmFjdG9yICogQVtpXVtqXTsKICAgICAgICAgICAgfQogICAgICAgICAgICBiW2tdICs9IGZhY3RvciAqIGJbaV07CiAgICAgICAgfQogICAgfQoKICAgIHZlY3Rvcjx2ZWN0b3I8ZG91YmxlPiA+IGdsb2JhbF9BKG4sIHZlY3Rvcjxkb3VibGU+KG4pKTsKICAgIHZlY3Rvcjxkb3VibGU+IGdsb2JhbF9iKG4pOwogICAgTVBJX0dhdGhlcigmQVswXVswXSwgcm93c19wZXJfcHJvY2VzcyAqIG4sIE1QSV9ET1VCTEUsICZnbG9iYWxfQVswXVswXSwgcm93c19wZXJfcHJvY2VzcyAqIG4sIE1QSV9ET1VCTEUsIDAsIE1QSV9DT01NX1dPUkxEKTsKICAgIE1QSV9HYXRoZXIoJmJbMF0sIHJvd3NfcGVyX3Byb2Nlc3MsIE1QSV9ET1VCTEUsICZnbG9iYWxfYlswXSwgcm93c19wZXJfcHJvY2VzcywgTVBJX0RPVUJMRSwgMCwgTVBJX0NPTU1fV09STEQpOwoKICAgIGlmIChyYW5rID09IDApIHsKICAgICAgICB2ZWN0b3I8ZG91YmxlPiB4KG4pOwogICAgICAgIGZvciAoaW50IGkgPSBuIC0gMTsgaSA+PSAwOyAtLWkpIHsKICAgICAgICAgICAgeFtpXSA9IGdsb2JhbF9iW2ldIC8gZ2xvYmFsX0FbaV1baV07CiAgICAgICAgICAgIGZvciAoaW50IGsgPSBpIC0gMTsgayA+PSAwOyAtLWspIHsKICAgICAgICAgICAgICAgIGdsb2JhbF9iW2tdIC09IGdsb2JhbF9BW2tdW2ldICogeFtpXTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgY291dCA8PCAiU29sdXRpb246XG4iOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgICAgIGNvdXQgPDwgInhbIiA8PCBpIDw8ICJdID0gIiA8PCB4W2ldIDw8IGVuZGw7CiAgICAgICAgfQogICAgfQp9CgppbnQgbWFpbihpbnQgYXJnYywgY2hhcioqIGFyZ3YpIHsKICAgIE1QSV9Jbml0KCZhcmdjLCAmYXJndik7CgogICAgaW50IHJhbmssIHNpemU7CiAgICBNUElfQ29tbV9yYW5rKE1QSV9DT01NX1dPUkxELCAmcmFuayk7CiAgICBNUElfQ29tbV9zaXplKE1QSV9DT01NX1dPUkxELCAmc2l6ZSk7CgogICAgdmVjdG9yPHZlY3Rvcjxkb3VibGU+ID4gQSgzLCB2ZWN0b3I8ZG91YmxlPigzKSk7CiAgICBBWzBdWzBdID0gMjsgQVswXVsxXSA9IDE7IEFbMF1bMl0gPSAtMTsKICAgIEFbMV1bMF0gPSAtMzsgQVsxXVsxXSA9IC0xOyBBWzFdWzJdID0gMjsKICAgIEFbMl1bMF0gPSAtMjsgQVsyXVsxXSA9IDE7IEFbMl1bMl0gPSAyOwoKICAgIHZlY3Rvcjxkb3VibGU+IGIoMyk7CiAgICBiWzBdID0gODsgYlsxXSA9IC0xMTsgYlsyXSA9IC0zOwoKICAgIGdhdXNzaWFuRWxpbWluYXRpb24oQSwgYiwgcmFuaywgc2l6ZSk7CgogICAgTVBJX0ZpbmFsaXplKCk7CgogICAgcmV0dXJuIDA7Cn0K