Submission #1298027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298027		Bahamin	Snake Escaping (JOI18_snake_escaping)	C++20	5 / 100	202 ms	131072 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 3;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

vector<pair<int, int>> qs[(1 << 3)];

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    int a[s.size()];
    for (int i = 0; i < s.size(); i++) a[i] = s[i] - '0';
    vector<pair<int, int>> al[(1 << 3)];
    for (int i = 0; i < (1 << n); i++) 
    {
        int mul = 1;
        int sum = 0;
        for (int j = 3; j < n; j++) sum += ((i & (1 << j)) ? 1 : 0) * mul, mul *= 3;
        al[i % (1 << 3)].push_back({sum, a[i]});
    }
    int ans[q];
    fill(ans, ans + q, 0);
    for (int p = 0; p < q; p++)
    {
        string t;
        cin >> t;
        reverse(all(t));
        vector<int> ms;
        int sum1 = 0;
        for (int i = 0; i < min(n, 3); i++) 
        {
            if (t[i] == '?') ms.push_back(i); 
            else sum1 += (1 << i) * (t[i] - '0');
        }
        int sum = 0;
        int mul = 1;
        for (int i = 3; i < n; i++) sum += (t[i] == '?' ? 2 : t[i] - '0') * mul, mul *= 3;
        for (int i = 0; i < (1 << ms.size()); i++)
        {
            int sum2 = sum1;
            for (int j = 0; j < ms.size(); j++) sum2 += ((i & (1 << j)) ? 1 : 0) * (1 << ms[j]);
            qs[sum2].push_back({p, sum});
        }
    }
    int mul = 1;
    for (int i = 3; i < n; i++) mul *= 3;
    int ma[mul];
    int po[13];
    po[0] = 1;
    for (int i = 1; i < 13; i++) po[i] = po[i - 1] * 3;
    for (int i = 0; i < mul; i++)
    {
        ma[i] = -1;
        int num = i;
        for (int j = 0; j < (n - 3); j++) 
        {
            if (num % 3 == 2) 
            {
                ma[i] = j;
                break;
            }
            num /= 3;
        }
    }
    for (int i = 0; i < (1 << 3); i++)
    {
        int dp[mul];
        fill(dp, dp + mul, 0);
        for (auto x : al[i]) dp[x.first] += x.second;
        // cout << i << " " << dp[0] << " " << qs[i] << "\n";
        for (int j = 0; j < mul; j++)
        {
            int ind = ma[j];
            if (ind == -1) continue;
            dp[j] = dp[j - po[ind]] + dp[j - 2 * po[ind]];
        }
        for (auto x : qs[i]) ans[x.first] += dp[x.second];
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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