Submission #467538

#	Time	Username	Problem	Language	Result	Execution time	Memory
467538		LucaIlie	Norela (info1cup18_norela)	C11	100 / 100	19 ms	384 KiB

norela

#include <stdio.h>

#define MAX_M 24

struct aaa {
    int usedSpells;
    long long xor;
};

struct aaa v[1 << (MAX_M / 2)];

long long spell[MAX_M];

int main() {
    int n, m, k, p, minUsedSpells, usedSpells, solMask, mask1, mask2, i, j;
    long long xor;

    scanf( "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        scanf( "%d", &k );
        spell[i] = 0;
        for ( j = 0; j < k; j++ ) {
            scanf( "%d", &p );
            spell[i] += ((long long)1 << (p - 1));
        }
    }

    for ( mask1 = 0; mask1 < (1 << (m / 2)); mask1++ ) {
        xor = 0;
        usedSpells = 0;
        for ( i = 0; i < m / 2; i++ ) {
            if ( ((mask1 >> i) & 1) == 1 ) {
                xor ^= spell[m - 1 - i];
                usedSpells++;
            }
        }
        v[mask1].xor = xor;
        v[mask1].usedSpells = usedSpells;
    }
    minUsedSpells = m + 1;
    solMask = -1;
    for ( mask2 = 0; mask2 < (1 << (m - m / 2)); mask2++ ) {
        xor = 0;
        usedSpells = 0;
        for ( i = 0; i < m - m / 2; i++ ) {
            if ( ((mask2 >> i) & 1) == 1 ) {
                xor ^= spell[m - m / 2 - 1 - i];
                usedSpells++;
            }
        }
        for ( mask1 = 0; mask1 < (1 << (m / 2)); mask1++ ) {
            if ( (v[mask1].xor ^ xor) == ((long long)1 << n) - 1 ) {
                if ( v[mask1].usedSpells + usedSpells < minUsedSpells ) {
                    minUsedSpells = v[mask1].usedSpells + usedSpells;
                    solMask = mask1 + mask2 * (1 << (m / 2));
                }
                else if ( v[mask1].usedSpells + usedSpells == minUsedSpells ) {
                    if ( mask1 + mask2 * (1 << (m / 2)) > solMask )
                        solMask = mask1 + mask2 * (1 << (m / 2));
                }
            }
        }
    }

    printf( "%d\n", minUsedSpells );
    for ( i = m - 1; i >= 0; i-- ) {
        if ( ((solMask >> i) & 1) == 1 )
            printf( "%d ", m - i );
    }

    return 0;
}

Compilation message (stderr)

norela.c: In function 'main':
norela.c:18:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf( "%d%d", &n, &m );
      |     ^~~~~~~~~~~~~~~~~~~~~~~
norela.c:20:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf( "%d", &k );
      |         ^~~~~~~~~~~~~~~~~
norela.c:23:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |             scanf( "%d", &p );
      |             ^~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25