Submission #1080931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080931		horiaboeriu	Norela (info1cup18_norela)	C++17	100 / 100	26 ms	420 KiB

norela

#include <stdio.h>
#include <stdlib.h>
#define MAXM 24
long long v[MAXM];
int m, min, rez;//voi tine trucurile din rezultat tot sub forma unei masti in loc de vector
long long p;
void bkt(int nr, long long x, int stare, int poz) {
    int i;
    if (nr < min) {
        if (x == p) {
            //este prima combinatie gasita cu acest nr de trucuri, deci este prima lexicografica
            rez = stare;
            min = nr;
        } else {
            for (i = poz + 1; i < m; i++) {
                bkt(nr + 1, x ^ v[i], stare ^ (1 << i), i);
            }
        }
    }
}
int main()
{
    int n, x, i, nr, j;
    //tin la fiecare m o masca cu cartile, adica le transform in putrei ale lui 2
    //dupa iau toate combinarile din cele m cu un backtracking si fac xorul mastilor din combinare
    //ca trebuie ca fiecare carte sa apara de un numar impar ca sa fie pe fata
    //si trebuie ca xorul lor sa fie (1 << n) - 1
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        scanf("%d", &nr);
        for (j = 0; j < nr; j++) {
            scanf("%d", &x);
            x--;//indexez cartile de la 0
            v[i] += ((long long)1 << x);
        }
    }
    p = ((long long)1 << n) - 1;//daca xorul este p, atunci toate cartile sunt pe fata
    min = m + 1;
    bkt(0, 0, 0, -1);
    printf("%d\n", min);
    for (i = 0; i < m; i++) {
        if (((1 << i) & rez) > 0) {//daca bitul i face parte din rezultat
            printf("%d ", i + 1);
        }
    }
    fputc('\n', stdout);
    return 0;
}

Compilation message (stderr)

norela.cpp: In function 'int main()':
norela.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
norela.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d", &nr);
      |         ~~~~~^~~~~~~~~~~
norela.cpp:32:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |             scanf("%d", &x);
      |             ~~~~~^~~~~~~~~~

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