Submission #1030715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030715		_callmelucian	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	487 ms	42204 KiB

snake_escaping

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int toxic[1 << 20], sosSub[1 << 20], sosSuper[1 << 20];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k, Q; cin >> k >> Q;
    for (int i = 0; i < (1 << k); i++) {
        char c; cin >> c;
        toxic[i] = sosSub[i] = sosSuper[i] = c - '0';
    }

    for (int i = 0; i < k; i++) {
        for (int mask = 0; mask < (1 << k); mask++) {
            if (mask & (1 << i)) sosSub[mask] += sosSub[mask ^ (1 << i)];
            else sosSuper[mask] += sosSuper[mask ^ (1 << i)];
        }
    }

    int full = (1 << k) - 1;
    while (Q--) {
        string s; cin >> s;
        reverse(all(s));

        int maskZ = 0, maskO = 0, maskQ = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '0') maskZ |= (1 << i);
            if (s[i] == '1') maskO |= (1 << i);
            if (s[i] == '?') maskQ |= (1 << i);
        }

        if (__builtin_popcount(maskQ) < 7) {
            int ans = 0;
            for (int sub = maskQ; sub; sub = (sub - 1) & maskQ)
                ans += toxic[sub | maskO];
            cout << ans + toxic[maskO] << "\n";
        }
        else if (__builtin_popcount(maskZ) < 7) {
            int ans = sosSuper[maskO];
            for (int sub = maskZ; sub; sub = (sub - 1) & maskZ) {
                if (__builtin_parity(sub)) ans -= sosSuper[sub | maskO];
                else ans += sosSuper[sub | maskO];
            }
            cout << ans << "\n";
        }
        else if (__builtin_popcount(maskO) < 7) {
            int ans = sosSub[maskO | maskQ];
            for (int sub = maskO; sub; sub = (sub - 1) & maskO) {
                int inv = maskO ^ sub;
                if (__builtin_parity(sub)) ans -= sosSub[inv | maskQ];
                else ans += sosSub[inv | maskQ];
            }
            cout << ans << "\n";
        }
    }

    return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for (int i = 0; i < s.size(); i++) {
      |                         ~~^~~~~~~~~~
snake_escaping.cpp:33:9: warning: unused variable 'full' [-Wunused-variable]
   33 |     int full = (1 << k) - 1;
      |         ^~~~

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