Submission #729399

#	Time	Username	Problem	Language	Result	Execution time	Memory
729399		Pring	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	2067 ms	18848 KiB

snake_escaping

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

#define int long long
typedef pair<int, int> pii;
#define endl '\n'

const int MXN = 1030, MXL = 10;
int l, q, n;
string s, t;
map<string, int> M;

bool MATCH(int x) {
    for (int i = 0; i < l; i++) {
        if (t[i] == '?') {
            x >>= 1;
            continue;
        }
        if ((t[i] & 1) ^ (x & 1)) return false;
        x >>= 1;
    }
    return true;
}

int SOLVE() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (MATCH(i)) {
            ans += s[i] - '0';
        }
    }
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> l >> q >> s;
    n = (1 << l);
    while (q--) {
        cin >> t;
        reverse(t.begin(), t.end());
        auto it = M.find(t);
        if (it == M.end()) {
            int x = SOLVE();
            cout << x << endl;
            M[t] = x;
        } else {
            cout << it -> second << endl;
        }
    }
    return 0;
}

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