Submission #255701

#	Time	Username	Problem	Language	Result	Execution time	Memory
255701		egekabas	Snake Escaping (JOI18_snake_escaping)	C++14	0 / 100	363 ms	26488 KiB

snake_escaping

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
int l, q;
string s;
const int n7 = 2187;
const int n13 = 1594323;
int val[1000009][2];
int av[n7][(1<<7)];
int child[n13][2];
int ans[1000009];
int tr[n13];
int dp[n13];
int a, b;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> l >> q;
    cin >> s;
    a = min(l, 7);
    b = l-a;
    for(int i = 0; i < q; ++i){
        string t;
        cin >> t;
        for(int j = 0; j < a; ++j){
            val[i][0] *= 3;
            if(t[j] != '?')
                val[i][0] += t[j]-'0';
            else
                val[i][0] += 2;
            
        }
        for(int j = a; j < l; ++j){
            val[i][1] *= 3;
            if(t[j] != '?')
                val[i][1] += t[j]-'0';
            else
                val[i][1] += 2;
        }
    }
    for(int i = 0; i < n7; ++i)
        for(int j = 0; j < (1<<j); ++j){
            av[i][j] = 1;
            int v1 = i, v2 = j;
            for(int k = 0; k < 7; ++k){
                if(v1%3 != 2 && v1%3 != v2%2)
                    av[i][j] = 0;
                v1 /= 3;
                v2 /= 2;
            }
        }
    for(int i = 0; i < n13; ++i){
        child[i][0] = child[i][1] = -1;
        int cur = 1;
        int val = i;
        for(int j = 0; j < 13; ++j){
            if(val%3 == 2){
                child[i][0] = i-cur;
                child[i][1] = i-2*cur;
                break;
            }
            cur *= 3;
            val /= 3;
        }
    }
    for(int i = 0; i < n13; ++i){
        int val = i;
        for(int j = 0; j < 13; ++j){
            tr[i] += (1<<j)*(val%3 > 0);
            val /= 3;
        }
    }
    for(int i = 0; i < (1<<a); ++i){
        for(int j = 0; j < n13; ++j){
            if(child[j][0] == -1){
                dp[j] = 0;
                if(tr[j] + (1<<b)*i < s.size())
                    dp[j] = s[tr[j]+(1<<b)*i]-'0';
            }
            else
                dp[j] = dp[child[j][0]]+dp[child[j][1]];
        }
        for(int j = 0; j < q; ++j){
            if(av[val[j][0]][i] == 0) continue;
            //cout << j << ' ' << i << '\n';
            ans[j] += dp[val[j][1]];
        }
    }
    for(int i = 0; i < q; ++i){
        //cout << tr[val[i][0]] << ' ';
        cout << ans[i] << '\n';
    
    }
} 

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:91:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(tr[j] + (1<<b)*i < s.size())
                    ~~~~~~~~~~~~~~~~~^~~~~~~~~~

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