Submission #1162428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162428		cpismylifeOwO	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1289 ms	20680 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = (1 << 20) + 5;

int l, q;
int arr[MaxN];

void Inp()
{
    cin >> l >> q;
    for (int x = 0; x < (1 << l); x++)
    {
        char a;
        cin >> a;
        arr[x] = a - '0';
    }
}

int po[2] = {1, -1};
int Pre1[MaxN];
int Pre2[MaxN];
string s;

int Sub1(int i, int cur)
{
    if (i >= l)
    {
        return arr[cur];
    }
    if (s[i] == '?')
    {
        return Sub1(i + 1, cur) + Sub1(i + 1, cur ^ (1 << i));
    }
    return Sub1(i + 1, cur ^ ((s[i] - '0') << i));
}

int Sub2(int i, int cur, bool md2)
{
    if (i >= l)
    {
        return Pre1[cur] * po[md2];
    }
    if (s[i] == '1')
    {
        return Sub2(i + 1, cur, md2 ^ 1) + Sub2(i + 1, cur ^ (1 << i), md2);
    }
    return Sub2(i + 1, cur ^ ((s[i] == '?') << i), md2);
}

int Sub3(int i, int cur, bool md2)
{
    if (i >= l)
    {
        return Pre2[cur] * po[md2];
    }
    if (s[i] == '0')
    {
        return Sub3(i + 1, cur, md2) + Sub3(i + 1, cur ^ (1 << i), md2 ^ 1);
    }
    return Sub3(i + 1, cur ^ ((s[i] == '1') << i), md2);
}

void Exc()
{
    for (int x = 0; x < (1 << l); x++)
    {
        Pre1[x] = arr[x];
        Pre2[x] = arr[((1 << l) - 1) ^ x];
    }
    for (int x = 0; x < l; x++)
    {
        for (int mask = 0; mask < (1 << l); mask++)
        {
            if (mask & (1 << x))
            {
                Pre1[mask] += Pre1[mask ^ (1 << x)];
                Pre2[mask] += Pre2[mask ^ (1 << x)];
            }
        }
    }
    for (int x = 0; x < (1 << l); x++)
    {
        int y = ((1 << l) - 1) ^ x;
        if (y > x)
        {
            swap(Pre2[x], Pre2[y]);
        }
    }
    for (int x = 1; x <= q; x++)
    {
        cin >> s;
        reverse(s.begin(), s.end());
        int cnt0 = 0, cnt1 = 0, cnt = 0;
        for (char y : s)
        {
            if (y == '?')
            {
                cnt++;
            }
            else if (y == '0')
            {
                cnt0++;
            }
            else
            {
                cnt1++;
            }
        }
        if (cnt <= min(cnt0, cnt1))
        {
            cout << Sub1(0, 0) << "\n";
        }
        else if (cnt1 <= min(cnt0, cnt))
        {
            cout << Sub2(0, 0, 0) << "\n";
        }
        else
        {
            cout << Sub3(0, 0, 0) << "\n";
        }
    }
}

int main()
{
    //freopen("D.INP", "r", stdin);
    //freopen("D.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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