Submission #340551

#	Time	Username	Problem	Language	Result	Execution time	Memory
340551		couplefire	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1900 ms	55684 KiB

snake_escaping

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

int len, q;
int dp[MAXN];
string s;
int ans[MAXN];
int pw[21];
int lowbit[MAXN];
int mp[MAXN];
int counter;
bool isSub[2187][128];
int p1[MAXN], p2[MAXN];

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> len >> q >> s;
    for(int i = 0; i<2187; i++){
        for(int j = 0; j<128; j++){
            isSub[i][j] = 1;
            int c1 = i, c2 = j;
            for(int k = 0; k < 7; k++){
                if((c1%3 != 2 && c2%2 != c1%3)) isSub[i][j] = 0;
                c1 /= 3, c2 /= 2;
            }
        }
    }
    pw[0] = 1; for(int i = 1; i<=20; i++) pw[i] = pw[i-1]*3;
    lowbit[0] = lowbit[1] = MAXN;
    for(int i = 2; i<MAXN; i++){
        if(i%3 == 2) lowbit[i] = 0;
        else lowbit[i] = lowbit[i/3]+1;
    }
    for(int i = 0; i<MAXN; i++){
        if(lowbit[i] >= MAXN) mp[counter++] = i;
    }
    for(int i = 0; i<q; i++){
        string ss; cin >> ss;
        reverse(ss.begin(), ss.end());
        int cur2 = 0;
        for(int j = 0; j<min(7, len); j++){
            if(ss[j] == '?') cur2 += pw[j]*2;
            else cur2 += pw[j]*(ss[j]-'0');
        }
        p2[i] = cur2;
        int cur1 = 0;
        for(int j = 7; j<len; j++){
            if(ss[j] == '?') cur1 += pw[j-7]*2;
            else cur1 += pw[j-7]*(ss[j]-'0');
        }
        p1[i] = cur1;
    }
    // for(int i = 0; i<100; i++) cout << lowbit[i] << " ";
    // cout << endl;
    for(int i = 0; i < min(128, (int)s.length()); i++){
        memset(dp, 0, sizeof dp);
        for(int j = 0, end = (1<<(max(len-7, 0))); j<end; j++) dp[mp[j]] = s[(j<<7)+i]-'0';
        for(int j = 0; j<((len >= 7) ? pw[len-7] : 1); j++){
            if(lowbit[j] < MAXN) dp[j] = dp[j-pw[lowbit[j]]]+dp[j-pw[lowbit[j]]*2];
        }
        for(int j = 0; j<q; j++){
            if(isSub[p2[j]][i]) ans[j] += dp[p1[j]];
        }
    }
    for(int i = 0; i<q; i++) cout << ans[i] << " ";
    cout << endl;
}

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