Submission #1204617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204617		chikien2009	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	846 ms	22008 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int l, q, t[1 << 20], sub[1 << 20], super[1 << 20], base, mask, res;
vector<int> a, b, c;
string s;

int main()
{
    setup();

    cin >> l >> q >> s;
    for (int i = 0; i < (1 << l); ++i)
    {
        sub[i] = super[i] = t[i] = s[i] - '0';
    }
    for (int i = 0; i < l; ++i)
    {
        for (int j = 0; j < (1 << l); ++j)
        {
            if ((j >> i) & 1)
            {
                super[j - (1 << i)] += super[j];
            }
        }
        for (int j = (1 << l) - 1; j >= 0; --j)
        {
            if ((j >> i) & 1)
            {
                sub[j] += sub[j - (1 << i)];
            }
        }
    }
    while (q--)
    {
        cin >> s;
        a = b = c = {};
        base = res = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '?')
            {
                a.push_back(s.size() - i - 1);
            }
            else if (s[i] == '0')
            {
                b.push_back(s.size() - i - 1);
            }
            else
            {
                c.push_back(s.size() - i - 1);
            }
        }
        if (a.size() < 7)
        {
            for (int i = 0; i < s.size(); ++i)
            {
                base += (s[i] == '?' ? 0 : s[i] - '0') * (1 << (s.size() - i - 1));
            }
            for (int i = 0; i < (1 << a.size()); ++i)
            {   
                mask = base;
                for (int j = 0; j < a.size(); ++j)
                {
                    mask += ((i >> j) & 1) * (1 << a[j]);
                }
                res += t[mask];
            }   
        }
        else if (b.size() < 7)
        {
            for (int i = 0; i < s.size(); ++i)
            {
                base += (s[i] == '?' ? 0 : s[i] - '0') * (1 << (s.size() - i - 1));
            }
            for (int i = 0; i < (1 << b.size()); ++i)
            {
                mask = 0;
                for (int j = 0; j < b.size(); ++j)
                {
                    mask += ((i >> j) & 1) * (1 << b[j]);
                }           
                if (__builtin_popcount(mask) & 1)
                {
                    res -= super[mask + base];
                }
                else
                {
                    res += super[mask + base];
                }
            }
        }
        else
        {
            for (int i = 0; i < s.size(); ++i)
            {
                base += (s[i] == '?' ? 1 : 0) * (1 << (s.size() - i - 1));
            }
            for (int i = 0; i < (1 << c.size()); ++i)
            {
                mask = 0;
                for (int j = 0; j < c.size(); ++j)
                {
                    mask += ((i >> j) & 1) * (1 << c[j]);
                }
                if ((c.size() - __builtin_popcount(mask)) & 1)
                {
                    res -= sub[mask + base];
                }
                else
                {
                    res += sub[mask + base];
                }
            }
        }
        cout << res << "\n";
    }
    return 0;
}

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