Submission #204075

#	Time	Username	Problem	Language	Result	Execution time	Memory
204075		Kastanda	Snake Escaping (JOI18_snake_escaping)	C++11	100 / 100	1450 ms	51696 KiB

snake_escaping

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 20, K = 12, M = 8, MXK = 531441, MXM = 6561, MAXQ = 1e6 + 9; // MXK = 3 ^ K, MXM = 3 ^ M
int n, q, k, m, RS[MAXQ], Val[MAXQ];
int L[MXK], R[MXK], B[MXK], dp[MXK];
char A[1 << N], Tmp[N];
vector < int > Q[MXM];
int main()
{
    scanf("%d%d%s", &n, &q, A);
    for (int i = 0; i < (1 << n); i ++)
        A[i] -= '0';
    k = min(K, n); m = n - k;
    for (int i = 0; i < q; i ++)
    {
        scanf("%s", Tmp);
        for (int j = 0; j < n; j ++)
        {
            if (Tmp[j] == '?')
                Tmp[j] = '2';
            Tmp[j] -= '0';
        }
        int pref = 0;
        for (int j = 0; j < m; j ++)
            pref = (pref << 1) + pref + Tmp[j];
        int suff = 0;
        for (int j = m; j < n; j ++)
            suff = (suff << 1) + suff + Tmp[j];
        Val[i] = suff;
        Q[pref].push_back(i);
    }
    int k3 = 1;
    for (int i = 0; i < k; i ++)
        k3 *= 3;
    for (int state = 0; state < k3; state ++)
    {
        int tmp = state;
        for (int j = 0; j < k; j ++)
            Tmp[j] = tmp % 3, tmp /= 3;
        int h = -1;
        for (int j = 0; j < k; j ++)
            if (Tmp[j] == 2)
                h = j;
        if (h == -1)
        {
            for (int j = 0; j < k; j ++)
                B[state] |= Tmp[j] << j;
            continue;
        }
        B[state] = -1;
        Tmp[h] = 0;
        for (int j = k - 1; ~ j; j --)
            L[state] = L[state] * 3 + Tmp[j];
        Tmp[h] = 1;
        for (int j = k - 1; ~ j; j --)
            R[state] = R[state] * 3 + Tmp[j];
    }
    for (int mask = 0; mask < (1 << m); mask ++)
    {
        for (int state = 0; state < k3; state ++)
        {
            if (B[state] != -1)
                dp[state] = A[(mask << k) | B[state]];
            else
                dp[state] = dp[L[state]] + dp[R[state]];
        }
        for (int sk = 0; sk < (1 << m); sk ++)
        {
            for (int j = 0; j < m; j ++)
            {
                if (sk >> j & 1)
                    Tmp[j] = 2;
                else
                    Tmp[j] = mask >> j & 1;
            }
            int pref = 0;
            for (int j = m - 1; ~ j; j --)
                pref = pref * 3 + Tmp[j];
            for (int i : Q[pref])
                RS[i] += dp[Val[i]];
        }
    }
    for (int i = 0; i < q; i ++)
        printf("%d\n", RS[i]);
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%s", &n, &q, A);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", Tmp);
         ~~~~~^~~~~~~~~~~

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