Submission #45119

#	Time	Username	Problem	Language	Result	Execution time	Memory
45119		model_code	Norela (info1cup18_norela)	C++17	100 / 100	134 ms	132064 KiB

norela

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>

#define MOD (1<<13)

using namespace std;

long long a[32], dp[17200000];
int cnt[MOD + 100], led[MOD + 100];

void precalc ()
{
    for (int i = 0; i <= MOD + 5; ++i)
    {
        int ci = i;
        for (; ci > 0; ci >>= 1)
        {
            if (ci & 1) ++cnt[i];
            ++led[i];
        }
    }
}

int main ()
{
  //  freopen ("input", "r", stdin);
   // freopen ("output3", "w", stdout);

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

    precalc ();

    assert (1 <= n && n <= 60);
    assert (1 <= m && m <= 24);

    for (int i = 1; i <= m; ++i)
    {
        int q;
        scanf ("%d", &q);

        assert (1 <= q && q <= n);

        for (int j = 1; j <= q; ++j)
        {
            int x;
            scanf ("%d", &x);

            assert (1 <= x && x <= n);

            a[m - i + 1] |= (1LL << (1LL * (x - 1)));
        }
    }

    int sol, mi = 400;
    for (int i = 1; i < (1 << m); ++i)
    {
        int bit;
        if (i >> 13) bit = led[i >> 13] + 13;
        else bit = led[i];

        dp[i] = (dp[i ^ (1 << (bit - 1))] ^ a[bit]);

        if (dp[i] == (1LL << (1LL * n)) - 1LL)
        {
            int x = cnt[i >> 13] + cnt[i & ((1 << 13) - 1)];
            if (mi >= x) mi = x, sol = i;
        }
    }

    printf ("%d\n", mi);
    assert (mi < 400);

    for (int j = m - 1; j >= 0; --j)
        if (sol & (1 << j)) printf ("%d ", m - j);

    printf ("\n");

    return 0;
}

Compilation message (stderr)

norela.cpp: In function 'int main()':
norela.cpp:32:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &n, &m);
     ~~~~~~^~~~~~~~~~~~~~~~~
norela.cpp:42:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &q);
         ~~~~~~^~~~~~~~~~
norela.cpp:49:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ("%d", &x);
             ~~~~~~^~~~~~~~~~

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