oj.uz

Submission #591012

# Submission time Handle Problem Language Result Execution time Memory
591012 2022-07-06T17:44:15 Z piOOE Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 4 ms 4440 KB 
#include <bits/stdc++.h>

using namespace std;

const int L = 20;

int S[1 << L], A[1 << L], B[1 << L], popcnt[1 << L];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i < 1 << L; ++i) {
        popcnt[i] = popcnt[i - (i & -i)] + 1;
    }
    int l, q;
    string s;
    cin >> l >> q >> s;
    for (int i = 0; i < 1 << l; ++i) {
        S[i] = A[i] = B[((1 << l) - 1) ^ i] = s[i] - '0';
    }
    for (int i = 0; i < l; ++i) {
        for (int mask = 0; mask < 1 << l; ++mask) {
            if (mask & 1 << i) {
                A[mask] += A[mask ^ 1 << i];
            }
        }
    }
    for (int i = 0; i < l; ++i) {
        for (int mask = 0; mask < 1 << l; ++mask) {
            if (mask & 1 << i) {
                B[mask] += B[mask ^ 1 << i];
            }
        }
    }
    while (q--) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());
        int mask0 = 0, mask1 = 0, mask2 = 0;
        for (int i = 0; i < l; ++i) {
            if (t[i] == '0') {
                mask0 ^= 1 << i;
            } else if (t[i] == '1') {
                mask1 ^= 1 << i;
            } else {
                mask2 ^= 1 << i;
            }
        }
        int ans = 0;
        if (popcnt[mask1] <= 6) {
            for (int mask = mask1; mask; mask = (mask - 1) & mask1) {
                ans += A[mask ^ mask2] * (popcnt[mask ^ mask1] & 1 ? -1 : 1);
            }
            ans += A[mask2] * (popcnt[mask1] & 1 ? -1 : 1);
        } else if (popcnt[mask0] <= 6) {
            for (int mask = mask0; mask; mask = (mask - 1) & mask0) {
                ans += B[mask ^ mask0] * (popcnt[mask ^ mask0] & 1 ? -1 : 1);
            }
            ans += B[mask2] * (popcnt[mask0] & 1 ? -1 : 1);
        } else {
            for (int mask = mask2; mask; mask = (mask - 1) & mask2) {
                ans += S[mask ^ mask1];
            }
            ans += S[mask1];
        }
        cout << ans << '\n';
    }
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 53.0

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

Subtask #5
0 / 25.0

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