Cod sursa(job #624619)

Utilizator vlad2901Vlad Berindei vlad2901 Data 22 octombrie 2011 15:54:18
Problema Balanta Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <cstdio>
#define MAXN 1024

#define UNKNOWN 0
#define HEAVY 1
#define LIGHT -1
#define OK MAXN

int c[MAXN];
int a[MAXN], b[MAXN];
int n, m;

/*
c[i] = 0 daca nu se stie nimic despre moneda i
c[i] = 1 daca moneda i a facut parte dintr-un grup 'mai greu'
c[i] = -1 daca moneda i a facut parte dintr-un grup 'mai usor'
c[i] = 2 daca moneda i sigur nu e nici mai grea nici mai usoara
*/

int main()
{
    int i, j, g = 0, u = 0, s = 0, nr, r;
    int min, max, bmin, bmax, nmin, nmax;
    freopen("balanta.in", "r", stdin);
    freopen("balanta.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for(i=0;i<m;++i)
    {
        scanf("%d", &nr);
        for(j=0;j<nr;++j)
        {
            scanf("%d", &a[j]);
        }

        for(j=0;j<nr;++j)
        {
            scanf("%d", &b[j]);
        }

        scanf("%d", &r);

        switch(r)
        {
            case 0:
                for(j=0;j<nr;++j)
                {
                    c[a[j]] = OK;
                }
                for(j=0;j<nr;++j)
                {
                    c[b[j]] = OK;
                }
                break;
            case 1:
                for(j=0;j<nr;++j)
                {
                    if(c[a[j]] < 0)
                        c[a[j]] = OK;
                    else if(c[a[j]] >= 0 && c[a[j]] != OK)
                        ++c[a[j]];

                }
                for(j=0;j<nr;++j)
                {
                    if(c[b[j]] > 0)
                        c[b[j]] = OK;
                    else if(c[b[j]] <= 0 && c[b[j]] != OK)
                        --c[b[j]];
                }
                break;
            case 2:
                for(j=0;j<nr;++j)
                {
                    if(c[a[j]] > 0)
                        c[a[j]] = OK;
                    else if(c[a[j]] <= 0 && c[a[j]] != OK)
                        --c[a[j]];
                }
                for(j=0;j<nr;++j)
                {
                    if(c[b[j]] < 0)
                        c[b[j]] = OK;
                    else if(c[b[j]] >= 0 && c[b[j]] != OK)
                        ++c[b[j]];
                }
                break;
        }
    }

    min = max = 0;
    bmin = bmax = -1;
    nmin = nmax = 0;
    for(i=1;i<=n;++i)
    {
        if(c[i] ==  max)
        {
            nmax++;
        }

        if(c[i] > max && c[i] != OK)
        {
            max = c[i];
            bmax = i;
            nmax = 1;
        }

        if(c[i] == min)
        {
            nmin++;
        }

        if(c[i] < min)
        {
            min = c[i];
            bmin = i;
            nmin = 1;
        }



        if(c[i] < 0)
        {
            ++u;
            continue;
        }
        if(c[i] == OK)
        {
            ++s;
            continue;
        }
        if(c[i] > 0)
        {
            ++g;
        }
    }

    if(s == n-1)
    {
        for(i=1;i<=n;++i)
        {
            if(c[i] != OK)
            {
                printf("%d\n", i);
                return 0;
            }
        }
    }

    if(u == 1 && g != 1)
    {
        for(i=1;i<=n;++i)
        {
            if(c[i] < 0)
            {
                printf("%d\n", i);
                return 0;
            }
        }
    }

    if(g == 1 && u != 1)
    {
        for(i=1;i<=n;++i)
        {
            if(c[i] > 1 && c[i] != OK)
            {
                printf("%d\n", i);
                return 0;
            }
        }
    }

    if(nmin == 1 && nmax != 1)
    {
        printf("%d\n", bmin);
        return 0;
    }

    if(nmax == 1 && nmin != 1)
    {
        printf("%d\n", bmax);
        return 0;
    }

    printf("0\n");
    return 0;
}