Submission #1144283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144283		monkey133	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	2095 ms	59624 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
 
// For clarity we use int for indices (since n is small) and ll for values that might be larger.
typedef long long ll;
 
// Fast bit–reversal for an n–bit number (assumes n <= 32)
inline int reverse_bits(int x, int n) {
    int r = 0;
    for (int i = 0; i < n; i++) {
        r = (r << 1) | (x & 1);
        x >>= 1;
    }
    return r;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    string toxic2;
    cin >> toxic2;
 
    // Precompute powers of 3.
    vector<ll> three(25);
    three[0] = 1;
    for (int i = 1; i < 25; i++)
        three[i] = three[i - 1] * 3;
 
    // Reorder the toxic string using bit–reversal.
    int totStates = 1 << n;
    string toxic = toxic2;
    for (int i = 0; i < totStates; i++) {
        int newmask = reverse_bits(i, n);
        toxic[i] = toxic2[newmask];
    }
 
    // m is the number of “prefix digits” (m <= 5)
    int m = min(5, n - 1);
    // dp is defined over states of length (n-m) digits (each digit in {0,1,2}).
    int dpSize = three[n - m]; 
    vector<int> dp(dpSize, 0);
 
    // Precompute hh[]: for each binary mask of length (n-m), convert it into a base–3 number 
    // where a 0–bit gives a digit 1 and a 1–bit gives a digit 2.
    int binarySize = 1 << (n - m);
    vector<int> hh(binarySize, 0);
    for (int i = 0; i < binarySize; i++){
        int sum = 0;
        for (int j = 0; j < n - m; j++){
            if (i & (1 << j))
                sum += 2 * three[j];
            else
                sum += three[j];
        }
        hh[i] = sum;
    }
 
    // Read query strings and compute a “mask” for each.
    // In our construction, each query’s value is stored as
    //   mask = sum_{j=0}^{n-1} (digit * three[j])
    // where digit is 1 for character '0' and 2 for character '1'.
    vector<ll> mask(q, 0);
    // Also precompute the lower m digits (low part) and the remaining high part.
    vector<int> low(q, 0);
    vector<int> high(q, 0);
    for (int i = 0; i < q; i++){
        string ss;
        cin >> ss;
        ll val = 0;
        for (int j = 0; j < n; j++){
            if (ss[j] == '0')
                val += three[j];
            else if (ss[j] == '1')
                val += 2 * three[j];
        }
        mask[i] = val;
        low[i] = val % three[m];       // lower m digits
        high[i] = val / three[m];        // remaining digits
    }
 
    // Precompute a lookup table for the prefix condition.
    // For each possible pref (a binary number with m bits) and each possible value x
    // (the lower m digits, where x is in [0, three[m]) corresponding to m ternary digits),
    // we require that:
    //   - if the i-th bit of pref is 0, then the i-th digit (base 3) is 0 or 1.
    //   - if the i-th bit of pref is 1, then the i-th digit is 0 or 2.
    int prefSize = 1 << m;
    int lowRange = three[m];
    vector<vector<bool>> valid(prefSize, vector<bool>(lowRange, true));
    for (int pref = 0; pref < prefSize; pref++){
        for (int x = 0; x < lowRange; x++){
            bool ok = true;
            int temp = x;
            for (int i = 0; i < m; i++){
                int d = temp % 3;
                temp /= 3;
                if (d == 1 && (pref & (1 << i))) { ok = false; break; }
                if (d == 2 && !(pref & (1 << i))) { ok = false; break; }
            }
            valid[pref][x] = ok;
        }
    }
 
    vector<int> ans(q, 0);
 
    // Outer loop over all possible prefixes.
    // (There are only 2^m possibilities, at most 32.)
    for (int pref = 0; pref < prefSize; pref++){
        // Reset dp.
        fill(dp.begin(), dp.end(), 0);
        // Initialize dp:
        // For each binary mask of length (n-m), we compute an index into our dp state
        // via hh[] and set dp[state] = toxic[ index2 ] where:
        //   index2 = pref + (j * (1 << m))
        // This corresponds to the way you rearranged toxic.
        int binarySize2 = 1 << (n - m);
        for (int j = 0; j < binarySize2; j++){
            int state = hh[j];
            int index2 = pref + j * (1 << m);
            dp[state] = toxic[index2] - '0';
        }
 
        // --- DP transformation (“SOS DP in base 3”) ---
        // Instead of the reverse j/while–loop, we iterate over every digit position.
        // For each position i (0 <= i < n-m) and each state j, if the digit at position i is nonzero,
        // add dp[j] to the dp state where that digit is decreased.
        for (int i = 0; i < (n - m); i++){
            for (int j = 0; j < dpSize; j++){
                int d = (j / three[i]) % 3;  // digit at position i
                if (d > 0)
                    dp[j - d * three[i]] += dp[j];
            }
        }
 
        // Process each query: check whether the lower m digits of mask (precomputed in low[])
        // are compatible with the current prefix (via the lookup table "valid"). If so,
        // add dp[high part] to the answer.
        for (int j = 0; j < q; j++){
            if (!valid[pref][low[j]])
                continue;
            ans[j] += dp[high[j]];
        }
    }
 
    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";
 
    return 0;
}

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