oj.uz

Submission #699630

# Submission time Handle Problem Language Result Execution time Memory
699630 2023-02-17T15:12:26 Z x0r Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll n, q, f[(1 << 20)], g[(1 << 20)], a[(1 << 20)];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < (1 << n); i++) {
        char c; cin >> c;
        a[i] = c - '0';
        f[i] = g[i] = c - '0';
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < (1 << n); j++)
            if (j >> i & 1)
                f[j] += f[j ^ (1 << i)];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < (1 << n); j++)
            if (!(j >> i & 1))
                g[j] += g[j ^ (1 << i)];
    while (q--) {
        string s; cin >> s;
        reverse(s.begin(), s.end());
        vector < int > v0, v1, v2;
        int msk1 = 0, msk2 = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') v0.push_back(i);
            if (s[i] == '1') {
                v1.push_back(i);
                msk1 ^= (1 << i);
            }
            if (s[i] == '?') {
                v2.push_back(i);
                msk2 ^= (1 << i);
            }
        }
        int len = min(v0.size(), min(v1.size(), v2.size()));
        if (len == (int)v0.size()) {
            ll res = 0;
            for (int j = 0; j < (1 << (int)v0.size()); j++) {
                int newmsk = msk1;
                for (int i = 0; i < (int)v0.size(); i++) if (j >> i & 1) newmsk ^= (1 << v0[i]);
                if (__builtin_popcount(j) & 1) res -= g[newmsk];
                else res += g[newmsk];
            }
            cout << res << '\n';
            continue;
        }
        if (len == (int)v1.size()) {
            ll res = 0;
            for (int j = 0; j < (1 << (int)v1.size()); j++) {
                int newmsk = msk2;
                for (int i = 0; i < (int)v1.size(); i++) if (j >> i & 1) newmsk ^= (1 << v1[i]);
                if ((__builtin_popcount(j) + v1.size()) & 1) res -= f[newmsk];
                else res += f[newmsk];
            }
            cout << res << '\n';
            continue;
        }
        if (len == (int)v2.size()) {
            ll res = 0;
            for (int j = 0; j < (1 << (int)v2.size()); j++) {
                int newmsk = 0;
                for (int i = 0; i < (int)v2.size(); i++) if (j >> i & 1) newmsk ^= (1 << v2[i]);
                res += a[newmsk];
            }
            cout << res << '\n';
            continue;
        }

    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -