oj.uz

Submission #698924

# Submission time Handle Problem Language Result Execution time Memory
698924 2023-02-14T20:16:22 Z finn__ Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -