Submission #1285574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285574		nemkho	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	332 KiB

snake_escaping

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = (1 << 20) + 5;
string s;
int q, h[N], dp_sub[N], dp_super[N], mask0, mask1, mask2, n;
void inp()
{
    cin >> n >> q;
    cin >> s;
}
void solve()
{
    for (int mask = 0; mask < (1 << n); mask++)
        h[mask] = s[mask] - '0';
    for (int mask = 0; mask < (1 << n); mask++)
        dp_sub[mask] = dp_super[mask] = h[mask];
    for (int k = 0; k < (1 << n); k++)
    {
        for (int mask = 0; mask < (1 << n); mask++)
        {
            if (mask & (1 << k))
                dp_sub[mask] += dp_sub[mask ^ (1 << k)];
        }
        for (int mask = (1 << n) - 1; mask >= 0; mask--)
        {
            if (!(mask & (1 << k)))
                dp_super[mask] += dp_super[mask ^ (1 << k)];
        }
    }
    while (q--)
    {
        string t;
        ll ans = 0;
        mask1 = mask2 = mask0 = 0;
        cin >> t;
        reverse(t.begin(), t.end());
        for (int i = 0; i < t.length(); i++)
        {
            if (t[i] == '?')
                mask2 |= (1 << i);
            else if (t[i] == '0')
                mask0 |= (1 << i);
            else if (t[i] == '1')
                mask1 |= (1 << i);
        }
        //cout << mask2 << "\n";
        if (__builtin_popcount(mask2) <= 6)
        {
            for (int sub = mask2; sub > 0; sub = (sub - 1) & mask2)
            {
               // cout << sub << "\n";
                ans += h[sub | mask1];
            }
            ans += h[mask1];
        }
        else if (__builtin_popcount(mask0) <= 6)
        {
            for (int sub = mask0; sub > 0; mask0 = (sub - 1) & mask0)
            {
                int cntbit = __builtin_popcount(sub);
                if (cntbit % 2 == 0)
                    ans -= dp_super[sub | mask1];
                else
                    ans += dp_super[sub | mask1];
            }
            ans -= dp_super[mask1];
        }
        else
        {
            for (int sub = mask1; sub > 0; sub = (sub - 1) & mask1)
            {
                int cntbit = __builtin_popcount(sub);
                if (cntbit % 2 == 0)
                    ans -= dp_sub[(sub ^ mask1) | mask2];
                else
                    ans += dp_sub[(sub ^ mask1) | mask2];
            }
            ans -= dp_sub[mask1 | mask2];
        }
        cout << ans << "\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inp();
    solve();
}

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