Submission #210493

#	Time	Username	Problem	Language	Result	Execution time	Memory
210493		SamAnd	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	653 ms	38520 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
const int N = 22, Q = 1000006;

int n, qq;
char a[(1 << N)];

bool so(const char a[], const char b[])
{
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] != b[i])
            return a[i] < b[i];
    }
    return false;
}
struct ban
{
    int i;
    char u[N];
};
bool operator<(const ban& a, const ban& b)
{
    return so(a.u, b.u);
}
ban b[Q];

int* t[N];

int ans[Q];

void rec(int i, int x, int u)
{
    if (i == n + 1)
    {
        ans[b[u].i] += t[n][x];
        return;
    }
    if (b[u].u[i] == '0')
        rec(i + 1, x, u);
    else if (b[u].u[i] == '1')
        rec(i + 1, x + (1 << (n - i)), u);
    else
    {
        rec(i + 1, x, u);
        rec(i + 1, x + (1 << (n - i)), u);
    }
}

int main()
{
    scanf("%d%d", &n, &qq);
    scanf(" %s", a);
    for (int i = 0; i < (1 << n); ++i)
        a[i] -= '0';
    for (int i = 0; i < qq; ++i)
    {
        b[i].i = i;
        scanf(" %s", (b[i].u + 1));
    }
    sort(b, b + qq);
    for (int j = 0; j <= n; ++j)
        t[j] = new int[(1 << (n - j))];
    for (int k = 0; k < (1 << n); ++k)
        t[0][k] = a[k];
    for (int i = 0; i < qq; ++i)
    {
        int s = 14;
        for (int j = 1; j <= min(n, 13); ++j)
        {
            if (i == 0 || b[i].u[j] != b[i - 1].u[j])
            {
                s = j;
                break;
            }
        }
        for (int j = s; j <= min(n, 13); ++j)
        {
            if (b[i].u[j] == '0')
            {
                for (int k = 0; k < (1 << (n - j)); ++k)
                {
                    t[j][k] = t[j - 1][k];
                }
            }
            else if (b[i].u[j] == '1')
            {
                for (int k = 0; k < (1 << (n - j)); ++k)
                {
                    t[j][k] = t[j - 1][k + (1 << (n - j))];
                }
            }
            else
            {
                for (int k = 0; k < (1 << (n - j)); ++k)
                {
                    t[j][k] = t[j - 1][k] + t[j - 1][k + (1 << (n - j))];
                }
            }
        }
        if (n <= 13)
        {
            ans[b[i].i] = t[n][0];
            continue;
        }
        rec(14, 0, i);
    }
    for (int i = 0; i < qq; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &qq);
     ~~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", a);
     ~~~~~^~~~~~~~~~
snake_escaping.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", (b[i].u + 1));
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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