Submission #140502

#	Time	Username	Problem	Language	Result	Execution time	Memory
140502		wasyl	Snake Escaping (JOI18_snake_escaping)	C++11	58 / 100	2045 ms	20432 KiB

snake_escaping

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

constexpr int lax = 20, qax = 1e6, nax = (1 << lax);

int l, q, n, tab[nax], pre[3][nax];
string s;

int id(const char c)
{
    if (c == '?') return 2;
    return c - '0';
}

int rek(const int t, string& s, const int v)
{
    for (int i = v; i < l; ++i)
        if (id(s[i]) == t)
        {
            int res = 0;
            if (t == 2)
            {
                s[i] = '0';
                res += rek(t, s, i + 1);
                s[i] = '1';
                res += rek(t, s, i + 1);
                s[i] = '?';
                return res;
            }
            if (t == 0)
            {
                s[i] = '?';
                res += rek(t, s, i + 1);
                s[i] = '1';
                res -= rek(t, s, i + 1);
                s[i] = '0';
                return res;
            }
            if (t == 1)
            {
                s[i] = '?';
                res += rek(t, s, i + 1);
                s[i] = '0';
                res -= rek(t, s, i + 1);
                s[i] = '1';
                return res;
            }

        }
    int msk = 0;
    for (int i = 0; i < l; ++i)
    {
        if (s[i] == '0') continue;
        if (s[i] == '1' and t == 2)
            msk += (1 << i);
        if (s[i] == '?')
            msk += (1 << i);
    }
    //cerr << s << ' ' << msk << ' ' << pre[t][msk] << '\n';
    return pre[t][msk]; //spo
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> l >> q;
    n = (1 << l);

    cin >> s;

    for (int i = 0; i < n; ++i)
        tab[i] = s[i] - '0';

    for (int i = 0; i < n; ++i)
        pre[0][i] = tab[(n - 1) - i];
    for (int i = 0; i < n; ++i)
        pre[1][i] = tab[i];
    for (int i = 0; i < n; ++i)
        pre[2][i] = tab[i];

    for (int i = 0; i < l; ++i)
        for (int j = 0; j < n; ++j)
            if ((1 << i) & j)
                pre[0][j] += pre[0][j - (1 << i)],
                pre[1][j] += pre[1][j - (1 << i)];

    for (int i = 0; i < q; ++i)
    {
        string s; cin >> s;
        reverse(begin(s), end(s));
        int zl[2] = {0, 0};
        for (char c : s)
            if (c == '0' or c == '1')
            ++zl[c - '0'];
        if (zl[0] <= lax / 3)
            cout << rek(0, s, 0) << '\n';
        else if (zl[1] <= lax / 3)
            cout << rek(1, s, 0) << '\n';
        else if (l - zl[0] - zl[1] <= lax / 3)
            cout << rek(2, s, 0) << '\n';
    }
}

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