Cod sursa(job #2616271)

Utilizator AokijiAlex M Aokiji Data 17 mai 2020 21:05:43
Problema Party Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream f("party.in");
ofstream g("party.out");
#define nmax 105

bool val[nmax], sat[1005];
int n, m, x[nmax], y[nmax], z[nmax], sol;

bool satisfiable()
{

    for (int i = 0; i < m; i ++)
    {
        bool mybool;
        if (z[i] == 0)
            mybool = val[x[i]] || val[y[i]];
        if (z[i] == 1)
            mybool = val[x[i]] || !val[y[i]];
        if (z[i] == 2)
            mybool = !val[x[i]] || val[y[i]];
        if (z[i] == 3)
            mybool = !val[x[i]] || !val[y[i]];
        if (!mybool)
        {
            bool luck = rand() % 2;
            if (luck)
                val[x[i]] = !val[x[i]];
            else
                val[y[i]] = !val[y[i]];
            return false;
        }
    }
    return true;
}

int main()
{
    f >> n >> m;
    for (int i = 0; i < m; i ++)
        f >> x[i] >> y[i] >> z[i];
    srand(time(NULL));
    for (int i = 1; i <= n; i ++)
        val[i] = rand() % 2;

    while(!satisfiable());

    for (int i = 1; i <= n; i ++)
        sol += val[i];
    g << sol << '\n';
    for (int i = 1; i <= n; i ++)
        if (val[i])
            g << i << '\n';

    f.close();
    g.close();
    return 0;

}