Cod sursa(job #2478880)

Utilizator mihai.alphamihai craciun mihai.alpha Data 22 octombrie 2019 20:36:53
Problema Algoritmul lui Gauss Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.28 kb
#include <bits/stdc++.h>

using namespace std;

bool X[505];
bool A[505][505];

inline int Mod(int nr)  {
    if(nr < 0)
        return -nr;
    return nr;
}

inline void solve()  {
    int N, M, l;
    scanf("%d%d%d", &N, &M, &l);
    vector <int> Size;
    Size.push_back(0);
    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= M + 1;j++)
            A[i][j] = 0;
    for(int i = 1;i <= M;i++)  {
        int aux;
        scanf("%d", &aux);
        Size.push_back(aux);
    }
    for(int i = 1;i <= l;i++)  {
        int aux;
        scanf("%d", &aux);
        A[aux][M + 1] = 1;
    }
    for(int i = 1;i <= M;i++)  {
        for(int j = 1;j <= Size[i];j++)  {
            int aux;
            scanf("%d", &aux);
            A[aux][i] = 1;
        }
    }
    int i = 1, j = 1;
    int k;
    bool aux;
       while(i <= N && j <= M)
    {
        //Cautam o linie k pentru care A[k][j] sa fie nenul. Folosim epsilonul pentru a nu lua in considerare micile erori de calcul.
        for(k = i; k <= N; ++k)
            if(A[k][j] != 0)
                break;

        //Daca nu gasim linia, necunoscuta j este variabila libera, incrementam pe j si trecem la pasul urmator.
        if(k == N+1)
        {
            ++j;
            continue;
        }

        //Interschimbam pe k cu i, daca este cazul.
        if(k != i)
            for(int l = 1; l <= M+1; ++l)
            {
                aux = A[i][l];
                A[i][l] = A[k][l];
                A[k][l] = aux;
            }

        //Pentru a usura calculele, impartim toate valorile de pe linia i la A[i][j], A[i][j] devenind 1.
        //Observam ca valorile de pe linia i si coloanele 1..j-1 sunt egale cu 0 de la pasii precedenti ai algoritmului,
        //deci nu e necesar sa le parcurgem pentru a le imparti.
//        for(int l = j+1; l <= M+1; ++l)
//            A[i][l] = A[i][l] / A[i][j];
//        A[i][j] = 1;

        //Scadem din ecuatiile i+1...N ecuatia i inmultita cu A[u][j], pentru a egala toti coeficientii de coloana j
        //a acestor linii la 0.
        for(int u = i+1; u <= N; ++u)
        {
            for(int l = j+1; l <= M+1; ++l)  {
                A[u][l] -= A[u][j] & A[i][l];
            }
            A[u][j] = 0;
        }

        ++i; ++j;
    }

    //Calculul necunoscutelor
    for(int i = N; i>0; --i)
        for(int j = 1; j <= M+1; ++j)
            if(A[i][j] != 0)
            {
                //Singura valoare nenegativa de pe linia i este rezultatul => sistemul nu are solutie.
                if(j == M+1)
                {
                    printf("-1\n");
                        return;
                }

                //Calculam pe necunoscuta j = rezultatul ecuatiei i - necunoscutele j+1...M inmultite cu coeficientii lor din aceasta ecuatie.
                X[j] = A[i][M+1];
                for(int k = j+1; k <= M; ++k)
                    X[j] -= X[k] & A[i][k];

                break;
            }

    //Afisare
    for(int i = 1; i <= M; ++i)  {
        if(X[i])
            printf("%d ", i);
    }
    printf("\n");
 }

int main()  {
	freopen("becuriacm.in", "r", stdin);
	freopen("becuriacm.out", "w", stdout);
	int t;
	cin >> t;
	while(t--)  {
        solve();
	}
	return 0;
}