oj.uz

Submission #522317

# Submission time Handle Problem Language Result Execution time Memory
522317 2022-02-04T15:06:43 Z fallingstar Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 332 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e6 + 2;

int f[1 << 20];
int ans[N];
unsigned char type[N];       // 255 if ?, otherwise 0/1 for majority

int get_mask(const string& s, char target)
{
    int mask = 0;
    for (auto ch : s) {
        mask <<= 1;
        mask |= ch == target;
    }
    return mask;
}

int main()
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int l, q; cin >> l >> q;
    string toxicity; cin >> toxicity;
    vector<string> queries(q);
    for (auto& s : queries) cin >> s;

    for (int i = 0; i < q; ++i) {
        int cnt[3] = {};
        for (auto ch : queries[i])
            ++cnt[ch == '?' ? 2 : ch - '0'];
        int mn = *min_element(cnt, cnt + 3);
        if (cnt[2] == mn) {
            int maskQ = get_mask(queries[i], '?');
            int mask1 = get_mask(queries[i], '1');
            for (int submask = maskQ; submask > 0; submask = (submask - 1) & maskQ)
                ans[i] += toxicity[mask1 | submask] - '0';
            ans[i] += toxicity[mask1] - '0';    // all 0
            type[i] = 255;
        }
        else
            type[i] = cnt[0] > cnt[1];
    }

    transform(toxicity.begin(), toxicity.end(), f, [](char ch) { return ch - '0'; });
    for (int b = 0; b < l; ++b)
        for (int i = 0; i < 1 << l; ++i)
            if ((i >> b) & 1)
                f[i] += f[i ^ (1 << b)];
    for (int i = 0; i < q; ++i)
        if (type[i] == 1) {
            int maskQ = get_mask(queries[i], '?');
            int mask1 = get_mask(queries[i], '1');
            for (int submask = mask1; submask > 0; submask = (submask - 1) & maskQ) // mask of 0 within 1
                ans[i] += f[maskQ | (mask1 ^ submask)] * (__builtin_popcount(submask) & 1 ? -1 : 1);
            ans[i] += f[maskQ | mask1];     // base: all 1 are ?
        }

    transform(toxicity.begin(), toxicity.end(), f, [](char ch) { return ch - '0'; });
    for (int b = 0; b < l; ++b)
        for (int i = (1 << l) - 1; i >= 0; --i)
            if (!((i >> b) & 1))
                f[i] += f[i ^ (1 << b)];
    int fullmask = (1 << l) - 1;
    for (int i = 0; i < q; ++i)
        if (type[i] == 0) {
            int maskQ = get_mask(queries[i], '?');
            int mask0 = get_mask(queries[i], '0');
            for (int submask = mask0; submask > 0; submask = (submask - 1) & maskQ) // mask of 1 within 0
                ans[i] += f[fullmask ^ (maskQ | (mask0 ^ submask))] * (__builtin_popcount(submask) & 1 ? -1 : 1);
            ans[i] += f[fullmask ^ (maskQ | mask0)];     // base: all 0 are ?
        }

    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 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 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 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 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 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 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 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 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -