Submission #1106004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106004		0x34c	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	591 ms	65536 KiB

snake_escaping

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

using namespace std;

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 = ?
    vector<vector<int>> bm0(1 << L, vector<int>(L + 1, 0)), bm1(1 << L, vector<int>(L + 1, 0));
    vector<int> val(1 << L, 0);
    for (int i = 0; i < s.size(); i++)
    {
        val[i] = s[i] - '0';
        bm0[i][0] = bm1[i][0] = val[i];
    }

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

    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][L];
            }

            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][L];
            }

            cout << res << endl;
        }
    }
}

Compilation message (stderr)

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

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