Submission #1256947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256947		tvgk	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1096 ms	17596 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e6 + 7;

int n, q, dp[mxN][2];
string s;
char chr[3] = {'0', '1', '?'};
vector<int> vc[3];

bool Check_bit(int j, int i)
{
    return (j >> i) & 1;
}

int BackTrack2(int j, int sum, vector<int>& v)
{
    if (j == v.size())
        return s[sum] - '0';

    int res = 0;
    for (int i = 0; i <= 1; i++)
        res += BackTrack2(j + 1, sum + (i << v[j]), v);
    return res;
}

int BackTrack1(int j, int sum, bool cnt, int id)
{
    if (j == vc[id].size())
    {
        if (!cnt)
            return dp[sum][id ^ 1];
        else
            return -dp[sum][id ^ 1];
    }

    int res = 0;
    for (int i = 0; i <= 1; i++)
    {
        if (id)
            res += BackTrack1(j + 1, sum - (i << vc[id][j]), cnt ^ i, id);
        else
            res += BackTrack1(j + 1, sum + (i << vc[id][j]), cnt ^ i, id);
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> q;
    cin >> s;

    for (int id = 0; id <= 1; id++)
    {
        for (int i = 0; i < (1 << n); i++)
            dp[i][id] = s[i] - '0';

        for (int u = 0; u < n; u++)
        {
            for (int i = 0; i < (1 << n); i++)
            {
                if (Check_bit(i, u) == id)
                    dp[i ^ (1 << u)][id] += dp[i][id];
            }
        }
    }

    for (int i = 1; i <= q; i++)
    {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());

        for (int u = 0; u < 3; u++)
            vc[u].clear();
        for (int j = 0; j < t.size(); j++)
        {
            for (int u = 0; u < 3; u++)
            {
                if (chr[u] == t[j])
                    vc[u].push_back(j);
            }
        }

        if (vc[2].size() <= n / 3)
        {
            int sum = 0;
            for (int i = 0; i < t.size(); i++)
            {
                if (t[i] != '?')
                    sum += (t[i] - '0') << i;
            }

            cout << BackTrack2(0, sum, vc[2]) << '\n';
        }
        else
        {
            bool id = vc[0].size() < vc[1].size();

            int sum = 0;
            for (int i = 0; i < t.size(); i++)
            {
                if (t[i] != id + '0')
                    sum += (id ^ 1) << i;
                else
                    sum += id << i;
            }

            cout << BackTrack1(0, sum, 0, id ^ 1) << '\n';
        }
    }
}

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