제출 #1290467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290467		windowwife	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	775 ms	20600 KiB

snake_escaping

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = (1 << 20) + 5;
int l, q, a[maxn], dp[maxn], dp2[maxn], m0, m1, mq, cnt0, cnt1, cntq, res;
char c;
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> l >> q;
    for (int i = 0; i < (1 << l); i++)
    {
        cin >> c;
        a[i] = dp[i] = dp2[i] = c - '0';
    }
    for (int j = 0; j < l; j++)
        for (int i = 0; i < (1 << l); i++)
            if ((i >> j) & 1)
            {
                dp[i] += dp[i ^ (1 << j)];
                dp2[i ^ (1 << j)] += dp2[i];
            }
    while (q--)
    {
        m0 = m1 = mq = 0;
        cnt0 = cnt1 = cntq = 0;
        res = 0;
        for (int j = l - 1; j >= 0; j--)
        {
            cin >> c;
            if (c == '0')
            {
                m0 ^= (1 << j);
                cnt0++;
            }
            else if (c == '1')
            {
                m1 ^= (1 << j);
                cnt1++;
            }
            else
            {
                mq ^= (1 << j);
                cntq++;
            }
        }
        if (cntq <= min(cnt0, cnt1))
        {
            for (int i = mq; true; i = (i - 1) & mq)
            {
                res += a[i ^ m1];
                if (i == 0) break;
            }
        }
        else if (cnt1 <= min(cntq, cnt0))
        {
            for (int i = m1; true; i = (i - 1) & m1)
            {
                if ((cnt1 ^ __builtin_popcount(i)) & 1) res -= dp[i ^ mq];
                else res += dp[i ^ mq];
                if (i == 0) break;
            }
        }
        else
        {
            for (int i = m0; true; i = (i - 1) & m0)
            {
                if (__builtin_popcount(i) & 1) res -= dp2[i ^ m1];
                else res += dp2[i ^ m1];
                if (i == 0) break;
            }
        }
        cout << res << '\n';
    }
}

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