Submission #171471

#	Time	Username	Problem	Language	Result	Execution time	Memory
171471		Akashi	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1757 ms	61656 KiB

snake_escaping

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

int n, q, L1, L2;
int m1[1000005], m2[1000005], ans[1000005];
int p3[25], p2[25];

char s[1048580];
char in[25];

int dp[1594330];
pair <int, int> son[1594330];

bool f[2200][130];

int main()
{
    scanf("%d%d", &n, &q);
    scanf("%s", s);

    p3[0] = 1;
    for(int i = 1; i <= 21 ; ++i) p3[i] = p3[i - 1] * 3;
    p2[0] = 1;
    for(int i = 1; i <= 21 ; ++i) p2[i] = p2[i - 1] * 2;

    if(n >= 10) L1 = 7, L2 = n - L1;
    else L1 = 1, L2 = n - L1;

    for(int mask = 0; mask < p3[L1] ; ++mask){
        for(int mask2 = 0; mask2 < p2[L1] ; ++mask2){
            bool ok = true;

            for(int i = 0; i < L1 ; ++i){
                int x = (mask % p3[i + 1]) / p3[i];
                int y = (mask2 & p2[i]) > 0;
                if(x == y || x == 2) continue ;
                ok = false; break ;
            }

            f[mask][mask2] = ok;
        }
    }

    for(int i = 1; i <= q ; ++i){
        scanf("%s", in);

        for(int j = 0; j < L1 ; ++j){
            int x;
            if(in[j] == '0') x = 0;
            else if(in[j] == '1') x = 1;
            else x = 2;
            m1[i] = m1[i] + x * p3[L1 - j - 1];
        }

        for(int j = L1; j < n ; ++j){
            int x;
            if(in[j] == '0') x = 0;
            else if(in[j] == '1') x = 1;
            else x = 2;
            m2[i] = m2[i] + x * p3[j - L1];
        }
    }

    for(int mask = 0; mask < p3[L2] ; ++mask){
        int mask2 = 0;
        bool found = false;
        for(int i = 0; i < L2 ; ++i){
            int x = (mask % p3[i + 1]) / p3[i];
            if(x == 2){
                found = true;
                son[mask] = {mask - x * p3[i], mask - x * p3[i] + p3[i]};
                break ;
            }
            else mask2 = mask2 + x * p2[L2 - i - 1];
        }

        if(!found) son[mask] = {mask2, -1};
    }

    int P = (1 << L1);
    for(int mask2 = 0; mask2 < P ; ++mask2){

        int ad = mask2 * p2[L2];
        for(int mask = 0; mask < p3[L2] ; ++mask){
            if(son[mask].second == -1) dp[mask] = s[son[mask].first + ad] - '0';
            else dp[mask] = dp[son[mask].first] + dp[son[mask].second];
        }

        for(int i = 1; i <= q ; ++i){
            if(f[m1[i]][mask2])
                ans[i] += dp[m2[i]];
        }
    }

    for(int i = 1; i <= q ; ++i)
        printf("%d\n", ans[i]);

    return 0;
}

Compilation message (stderr)

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

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