Submission #1290519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290519		yoshi_33550336	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2097 ms	57428 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
int L, K;
short PreCalc[4096][6561];
vector<pair<int, int>> PreComp;
void recursion(int i, int mask1, int mask2, int value, int pw)
{
    if (i == L - K)
    {
        for (int k = 0; k < (1 << (L - K)); k++)
            if ((mask1 & k) == k && (mask2 & k) == mask2)
                PreComp.push_back({value, k});
    }
    else
    {
        recursion(i + 1, mask1, mask2, value, pw * 3);
        recursion(i + 1, mask1 | (1 << i), mask2 | (1 << i), value + pw, pw * 3);
        recursion(i + 1, mask1 | (1 << i), mask2, value + 2 * pw, pw * 3);
    }
}
void Yoshi()
{
    int Q;
    string s;
    cin >> L >> Q >> s;
    K = (L <= 13 ? 6 : 12);
    if (L <= K)
    {
        while (Q--)
        {
            string t;
            cin >> t;
            reverse(t.begin(), t.end());
            int mask1 = 0, mask2 = 0;
            for (int i = 0; i < t.size(); i++)
            {
                if (t[i] == '?')
                    mask1 |= (1 << i);
                else if (t[i] == '1')
                    mask1 |= (1 << i), mask2 |= (1 << i);
            }
            int r = 0;
            for (int i = 0; i < (1 << L); i++)
                if ((mask1 & i) == i && (mask2 & i) == mask2)
                    r += s[i] - '0';
            cout << r << endl;
        }
    }
    else
    {
        recursion(0, 0, 0, 0, 1);
        for (int low = 0; low < (1 << K); low++)
        {
            int a[1 << (L - K)];
            for (int i = 0; (i << K) < s.size(); i++)
                a[i] = max(0, s[(i << K) + low] - '0');
            for (auto &[x, y] : PreComp)
                PreCalc[low][x] += a[y];
        }
        while (Q--)
        {
            string t;
            cin >> t;
            reverse(t.begin(), t.end());
            int mask1 = 0, mask2 = 0;
            for (int i = 0; i < K; i++)
            {
                if (t[i] == '?')
                    mask1 |= (1 << i);
                else if (t[i] == '1')
                    mask1 |= (1 << i), mask2 |= (1 << i);
            }
            int pw = 1, g = 0;
            for (int i = K; i < t.size(); i++)
            {
                if (t[i] == '1')
                    g += pw;
                else if (t[i] == '?')
                    g += 2 * pw;
                pw *= 3;
            }
            int r = 0;
            for (int i = 0; i < (1 << K); i++)
                if ((mask1 & i) == i && (mask2 & i) == mask2)
                    r += PreCalc[i][g];
            cout << r << endl;
        }
    }
}
signed main()
{
#ifndef yoshi_likes_e4
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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