Submission #1180623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180623		miniob	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	2091 ms	10008 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

int dp[1048583];
int bity[1048583];

bitset<20> temp;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int l, q;
    string s1, s2;
    cin >> l >> q >> s1;
    int n = 1 << l;
    for (int i = 0; i < n; i++)
    {
        dp[i] = s1[i] - '0';
    }
    for(int i = 0; i < n; i++)
    {
    	temp = i;
    	bity[i] = temp.count();
    }
    for (int i = 0; i < l; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((j & (1 << i)) == 0)
            {
            	dp[j] += dp[j | (1 << i)];
            }
        }
    }
    while(q--)
    {
        cin >> s2;
        int jedy = 0, zero = 0;
        for (int i = 0; i < l; i++)
        {
            if (s2[i] == '1')
            {
                jedy |= (1 << (l - 1 - i));
            } 
            else if (s2[i] == '0') 
            {
                zero |= (1 << (l - 1 - i));
            }
        }
        int odp = 0, cur = zero;
        while(true)
        {
        	//cout << cur << endl;
            if (bity[cur] % 2 == 0)
            {
            	odp += dp[jedy | cur];
            }
            else
            {
            	odp -= dp[jedy | cur];
            }
            if (cur == 0)
            {
            	break;
            }
            cur = (cur - 1) & zero;
        }
        cout << odp << endl;
    }
    return 0;
}

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