Submission #1176127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176127		TrendBattles	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	0 ms	324 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
using lli = long long int;

#define INFILE "snake.inp"
#define OUTFILE "snake.out"

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    int L, Q; cin >> L >> Q;
    string digits; cin >> digits;

    vector <int> value(1 << L), or_sum(1 << L), and_sum(1 << L);
    for (int m = 0; m < (1 << L); ++m) {
        value[m] = or_sum[m] = digits[m] - '0';
    }

    for (int b = 0; b < L; ++b) {
        for (int m = 0; m < (1 << L); ++m) {
            if (m >> b & 1) {
                and_sum[m] += and_sum[m ^ (1 << b)];
            } else {
                or_sum[m] += or_sum[m ^ (1 << b)];
            }
        }
    }
    
    for (int _ = 0; _ < Q; ++_) {
        string que; cin >> que;
        int ques_mask = 0, zero_mask = 0, one_mask = 0;
        for (int i = 0; i < L; ++i) {
            if (que[i] == '?') ques_mask ^= 1 << L - i - 1;
            else if (que[i] == '0') zero_mask ^= 1 << L - i - 1;
            else one_mask ^= 1 << L - i - 1;
        }

        int ans = 0;
        if (__builtin_popcount(ques_mask) <= L / 3) {
            for (int x = ques_mask; x >= 0; x = (x - 1) & ques_mask) {
                ans += value[one_mask ^ x];
                if (x == 0) break;
            }
        } else if (__builtin_popcount(zero_mask) <= L / 3) {
            for (int x = zero_mask; x >= 0; x = (x - 1) & zero_mask) {
                if (__builtin_popcount(x) & 1) {
                    ans -= or_sum[x ^ one_mask];
                } else {
                    ans += or_sum[x ^ one_mask];
                }
                if (x == 0) break;
            }
        } else {
            for (int x = one_mask; x >= 0; x = (x - 1) & one_mask) {
                if (__builtin_popcount(x ^ one_mask) & 1) {
                    ans -= and_sum[x];
                } else {
                    ans += and_sum[x];
                }
                if (x == 0) break;
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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