Submission #1180636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180636		miniob	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2094 ms	21736 KiB

snake_escaping

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

int dp[1048583];
int dp2[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';
        dp2[i] = dp[i];
    }
    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)];
            }
            else 
            {
            	dp2[j] += dp2[j - (1 << i)];
            }
        }
    }
    while(q--)
    {
        cin >> s2;
        int jedy = 0, zero = 0, ilez = 0, ileze = 0, ilejed = 0, zapyt = 0;
        for (int i = 0; i < l; i++)
        {
            if (s2[i] == '1')
            {
            	ilejed++;
                jedy |= (1 << (l - 1 - i));
            } 
            else if (s2[i] == '0') 
            {
            	ileze++;
                zero |= (1 << (l - 1 - i));
            }
            else 
            {
            	ilez++;	
            	zapyt |= (1 << (l - 1 - i));
            }
        }
        int odp = 0;
        if(ileze <= 6)
        {
	        int 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;
	        }
        }
        else /*if(ilejed <= 6)*/
        {
	        int cur = jedy;
	        while(true)
	        {
	        	//cout << cur << endl;
	            if ((bity[jedy] - bity[cur]) % 2 == 0)
	            {
	            	odp += dp2[zapyt | cur];
	            }
	            else
	            {
	            	odp -= dp2[zapyt | cur];
	            }
	            if (cur == 0)
	            {
	            	break;
	            }
	            cur = (cur - 1) & jedy;
	        }
        }
        cout << odp << endl;
    }
    return 0;
}

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