Submission #1180649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180649		miniob	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1415 ms	25932 KiB

snake_escaping

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

int org[1048583];
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';
        org[i] = 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;
        vector<int> zapi;
        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++;	
            	zapi.push_back(l - 1 - i);
            	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;
	        }
        }
        else
        {
        	bitset<6> temp2;
        	for(int i = 0; i < (1 << ilez); i++)
        	{
        		int curr = jedy;
        		temp2 = i;
        	//	cout << (i << (6 - ilez)) << endl;
        		for(int j = 0; j < ilez; j++)
        		{
        			//cout << temp2[j] << " ";
        			curr |= (temp2[j] << zapi[j]);
        		}
        		//cout << endl;
        		//cout << curr << endl;
        		odp += org[curr];
        	}
        }
        cout << odp << endl;
    }
    return 0;
}

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