Submission #698924

#	Time	Username	Problem	Language	Result	Execution time	Memory
698924		finn__	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	340 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

#define popcount(x) __builtin_popcount(x)

char snakes[1 << 20];
unsigned v[1 << 20], super[1 << 20], sub[1 << 20];

int main()
{
    size_t l, q;
    scanf("%zu %zu %s", &l, &q, snakes);

    for (size_t i = 0; i < 1U << l; i++)
        super[i] = sub[i] = v[i] = snakes[i] - '0';

    for (size_t i = 0; i < l; i++)
        for (size_t j = 0; j < 1U << l; j++)
            if (j & (1 << i))
                sub[j] += sub[j ^ (1 << i)];
            else
                super[j] += super[j ^ (1 << i)];

    char s[20];
    while (q--)
    {
        scanf("%s", s);
        unsigned a = 0, b = 0, c = 0, ans = 0;
        for (size_t i = 0; i < l; i++)
        {
            a <<= 1, b <<= 1, c <<= 1;
            a |= s[i] == '0', b |= s[i] == '1', c |= s[i] == '?';
        }

        if (popcount(a) <= popcount(b) && popcount(a) <= popcount(c))
        {
            ans = super[b];
            for (unsigned i = a; i; i = (i - 1) & a)
                ans += super[b | i] * ((popcount(i) & 1) ? -1 : 1);
        }
        else if (popcount(b) <= popcount(a) && popcount(b) <= popcount(c))
        {
            ans = sub[c];
            for (unsigned i = b; i; i = (i - 1) & b)
                ans += sub[c | i] * ((popcount(b ^ i) & 1) ? -1 : 1);
        }
        else
        {
            ans = v[b];
            for (unsigned i = c; i; i = (i - 1) & c)
                ans += v[b | i];
        }

        printf("%u\n", ans);
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%zu %zu %s", &l, &q, snakes);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%s", s);
      |         ~~~~~^~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25