Submission #1106006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106006		0x34c	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1282 ms	52712 KiB

snake_escaping

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'

using namespace std;

const int MX_L = 20;
int bm0[1 << MX_L][2], bm1[1 << MX_L][2], val[1 << MX_L];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int L, Q;
    cin >> L >> Q;

    string s;
    cin >> s;

    // in bm0, 1 = ?; in bm1, 0 = ?
    int prv = 0, cur = 1;
    for (int i = 0; i < s.size(); i++)
    {
        val[i] = s[i] - '0';
        bm0[i][prv] = bm1[i][prv] = val[i];
    }

    for (int j = 1; j <= L; j++)
    {
        for (int i = 0; i < (1 << L); i++)
        {
            if (i & (1 << (j - 1)))
            {
                bm0[i][cur] = bm0[i][prv] + bm0[i ^ (1 << (j - 1))][prv];
                bm1[i][cur] = bm1[i][prv];
            }
            else
            {
                bm0[i][cur] = bm0[i][prv];
                bm1[i][cur] = bm1[i][prv] + bm1[i ^ (1 << (j - 1))][prv];
            }
        }
        swap(cur, prv);
    }
    swap(cur, prv);

    while (Q--)
    {
        string t;
        cin >> t;

        int sz = t.size() - 1;

        int cnt_0 = 0, cnt_1 = 0, cnt_q = 0;
        vector<int> p0, p1, pq;
        for (int i = 0; i < t.size(); i++)
            if (t[i] == '0')
            {
                cnt_0++;
                p0.push_back(i);
            }
            else if (t[i] == '1')
            {
                cnt_1++;
                p1.push_back(i);
            }
            else
            {
                cnt_q++;
                pq.push_back(i);
            }

        int mn = min({cnt_0, cnt_1, cnt_q});
        if (mn == cnt_q)
        {
            int bit = 0;
            for (int j = 0; j < t.size(); j++)
            {
                if (t[j] == '1')
                    bit |= (1 << (sz - j));
            }

            int res = 0;
            for (int add = 0; add < (1 << cnt_q); add++)
            {
                int bit2 = bit;
                for (int j = 0; j < cnt_q; j++)
                {
                    if (add & (1 << j))
                        bit2 |= (1 << (sz - pq[j]));
                }

                res += val[bit2];
            }

            cout << res << endl;
        }
        else if (mn == cnt_0)
        {
            // we do PIE
            int bit = 0;
            for (int j = 0; j < t.size(); j++)
            {
                if (t[j] == '1')
                    bit |= (1 << (sz - j));
            }

            int res = 0;
            for (int add = 0; add < (1 << cnt_0); add++)
            {
                int bit2 = bit;
                int cnt = __builtin_popcount(add);
                for (int j = 0; j < cnt_0; j++)
                {
                    if (add & (1 << j))
                        bit2 |= (1 << (sz - p0[j]));
                }

                res += (cnt % 2 == 1 ? -1 : 1) * bm1[bit2][cur];
            }

            cout << res << endl;
        }
        else
        {
            // we do PIE too
            int bit = 0;
            for (int j = 0; j < t.size(); j++)
            {
                if (t[j] == '1' || t[j] == '?')
                    bit |= (1 << (sz - j));
            }

            int res = 0;
            for (int add = 0; add < (1 << cnt_1); add++)
            {
                int bit2 = bit;
                int cnt = __builtin_popcount(add);
                for (int j = 0; j < cnt_1; j++)
                {
                    if (add & (1 << j))
                        bit2 ^= (1 << (sz - p1[j]));
                }

                res += (cnt % 2 == 1 ? -1 : 1) * bm0[bit2][cur];
            }

            cout << res << endl;
        }
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < s.size(); i++)
      |                     ~~^~~~~~~~~~
snake_escaping.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (int i = 0; i < t.size(); i++)
      |                         ~~^~~~~~~~~~
snake_escaping.cpp:79:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for (int j = 0; j < t.size(); j++)
      |                             ~~^~~~~~~~~~
snake_escaping.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int j = 0; j < t.size(); j++)
      |                             ~~^~~~~~~~~~
snake_escaping.cpp:130:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             for (int j = 0; j < t.size(); j++)
      |                             ~~^~~~~~~~~~

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