Cod sursa(job #3234765)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 11 iunie 2024 18:00:48
Problema Algoritmul lui Gauss Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
#include <bits/stdc++.h>
#include <iomanip>
#include <unistd.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;
using ld = long double;

void gpp(vector<vector<double>> &a, size_t n, size_t m, const double eps) {
  auto get_first_nonzero = [n, eps](vector<vector<double>> &a, size_t column, size_t starting_line) {
    for (size_t line = starting_line; line < n; ++line)
      if (abs(a[line][column]) > eps)
        return line;

    return n;
  };

  for (size_t curr_line = 0, curr_column = 0; curr_line < n && curr_column < m; ++curr_line) {
    if (abs(a[curr_line][curr_column]) < eps) {
      size_t aux_line = get_first_nonzero(a, curr_column, curr_line + 1);
      if (aux_line != n) {
        a[curr_line].swap(a[aux_line]);
      }
    }

    if (abs(a[curr_line][curr_column]) >= eps) {
      for (size_t column = curr_column + 1; column <= m; ++column)
        a[curr_line][column] /= a[curr_line][curr_column];
      a[curr_line][curr_column] = 1;

      for (size_t line = curr_line + 1; line < n; ++line) {
        for (size_t column = curr_column + 1; column <= m; ++column)
          a[line][column] -= a[line][curr_column] * a[curr_line][column];
        a[line][curr_column] = 0;
      }

      ++curr_column;
    }
  }
}

optional<vector<double>> solve_triangular(vector<vector<double>> &a, size_t n, size_t m, const double eps) {
  vector<double> x(m);

  auto get_first_nonzero = [m, eps](vector<vector<double>> &a, ssize_t line) {
    for (size_t column = 0; column <= m; ++column)
      if (abs(a[line][column]) > eps)
        return column;

    return m + 1;
  };

  for (ssize_t line = n - 1; line >= 0; --line) {
    size_t column = get_first_nonzero(a, line);
    if (column == m + 1)
      continue;

    if (column == m)
      return nullopt;

    x[column] = a[line][m];
    for (size_t col = m - 1; col > column; --col)
      x[column] -= a[line][col] * x[col];
  }

  return x;
}

void solve() {
  size_t n, m;
  cin >> n >> m;

  vector<vector<double>> a(n, vector<double>(m + 1));
  for (auto &line : a)
    for (auto &elem : line)
      cin >> elem;

  gpp(a, n, m, 1e-15);
  auto sol = solve_triangular(a, n, m, 1e-15);

  if (!sol.has_value()) {
    cout << "Imposibil\n";
  } else {
    for (auto x : sol.value())
      cout << setprecision(10) << fixed << x << ' ';
    cout << '\n';
  }
}

int main() {
  freopen("gauss.in", "r", stdin);
  freopen("gauss.out", "w", stdout);
  int t = 1;
  // cin >> t;
  while (t--)
    solve();

  return 0;
}