oj.uz

Submission #467535

# Submission time Handle Problem Language Result Execution time Memory
467535 2021-08-23T12:52:57 Z LucaIlie Norela (info1cup18_norela) C
75 / 100
 800 ms 324 KB 
#include <stdio.h>

#define MAX_M 24

long long spell[MAX_M];

int main() {
    int n, m, k, p, minUsedSpells, usedSpells, solMask, mask, 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));
        }
    }

    minUsedSpells = m + 1;
    solMask = -1;
    for ( mask = 0; mask < (1 << m); mask++ ) {
        xor = 0;
        usedSpells = 0;
        for ( i = 0; i < m; i++ ) {
            if ( ((mask >> i) & 1) == 1 ) {
                xor ^= spell[m - 1 - i];
                usedSpells++;
            }
        }
        if ( xor == ((long long)1 << n) - 1 ) {
            if ( usedSpells <= minUsedSpells ) {
                minUsedSpells = usedSpells;
                solMask = mask;
            }
        }
    }

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

    return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 204 KB Output is correct
2 Correct 17 ms 268 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 18 ms 272 KB Output is correct
5 Correct 18 ms 204 KB Output is correct
6 Correct 17 ms 272 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 204 KB Output is correct
2 Correct 17 ms 268 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 18 ms 272 KB Output is correct
5 Correct 18 ms 204 KB Output is correct
6 Correct 17 ms 272 KB Output is correct
7 Correct 72 ms 272 KB Output is correct
8 Correct 140 ms 256 KB Output is correct
9 Correct 139 ms 204 KB Output is correct
10 Correct 157 ms 256 KB Output is correct
11 Correct 147 ms 272 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 204 KB Output is correct
2 Correct 17 ms 268 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 18 ms 272 KB Output is correct
5 Correct 18 ms 204 KB Output is correct
6 Correct 17 ms 272 KB Output is correct
7 Correct 72 ms 272 KB Output is correct
8 Correct 140 ms 256 KB Output is correct
9 Correct 139 ms 204 KB Output is correct
10 Correct 157 ms 256 KB Output is correct
11 Correct 147 ms 272 KB Output is correct
12 Correct 142 ms 204 KB Output is correct
13 Correct 283 ms 204 KB Output is correct
14 Correct 292 ms 256 KB Output is correct
15 Correct 284 ms 252 KB Output is correct
16 Correct 290 ms 252 KB Output is correct
17 Correct 290 ms 324 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 204 KB Output is correct
2 Correct 17 ms 268 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 18 ms 272 KB Output is correct
5 Correct 18 ms 204 KB Output is correct
6 Correct 17 ms 272 KB Output is correct
7 Correct 72 ms 272 KB Output is correct
8 Correct 140 ms 256 KB Output is correct
9 Correct 139 ms 204 KB Output is correct
10 Correct 157 ms 256 KB Output is correct
11 Correct 147 ms 272 KB Output is correct
12 Correct 142 ms 204 KB Output is correct
13 Correct 283 ms 204 KB Output is correct
14 Correct 292 ms 256 KB Output is correct
15 Correct 284 ms 252 KB Output is correct
16 Correct 290 ms 252 KB Output is correct
17 Correct 290 ms 324 KB Output is correct
18 Correct 604 ms 260 KB Output is correct
19 Correct 610 ms 256 KB Output is correct
20 Execution timed out 1093 ms 204 KB Time limit exceeded
21 Halted 0 ms 0 KB -