Submission #1304042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304042		anhkiet	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	918 ms	34052 KiB

snake_escaping

#include <bits/stdc++.h>

#define f first
#define s second
// #define int long long
#define sz(x) (int)(x).size()
#define MASK(x) (1ll << (x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll INF = 1e9 + 5;
const int mod = 1e9 + 7, base = 256, S = 320;

template <class X, class Y>
bool maximize(X &x, const Y &y) {
    if (x < y) {
        x = y; return true;
    }
    return false;
}

template <class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x > y) {
        x = y; return true;
    }
    return false;
}

template <class X, class Y>
void add(X &x, const Y &y) {
    if ((x += y) >= mod) x -= mod;
}

template <class X, class Y>
void sub(X &x, const Y &y) {
    if ((x -= y) < 0) x += mod;
}

template <class T>
void compress(vector <T> &v) {
    sort(all(v)); v.resize(unique(all(v)) - v.begin());
}

const int N = MASK(20) + 5;

int n, q;
string s;
ll f[N], g[N], a[N];

void solve() {
    cin >> n >> q >> s;
    for (int i = 0; i < sz(s); i++) {
        a[i] = s[i] - '0';
    }

    int m = MASK(n);
    for (int i = 0; i < m; i++) {
        f[i] = g[i] = a[i];
    }

    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < m; mask++) {
            if (mask >> i & 1) f[mask] += f[mask ^ MASK(i)];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < m; mask++) {
            if (!(mask >> i & 1)) g[mask] += g[mask ^ MASK(i)];
        }
    }

    while (q--) {
        string str;
        cin >> str;

        reverse(all(str));
        int d1 = 0, d2 = 0, d3 = 0;
        int mask1 = 0, mask2 = 0, mask3 = 0;

        for (int i = 0; i < n; i++) {
            if (str[i] == '0') {
                d1++;
                mask1 |= MASK(i);
            }
            if (str[i] == '1') {
                d2++;
                mask2 |= MASK(i);
            }
            if (str[i] == '?') {
                d3++;
                mask3 |= MASK(i);
            }
        }

        ll res = 0;
        if (d1 <= 6) {
            res = g[mask2];
            for (int sub = mask1; sub > 0; sub = (sub - 1) & mask1) {
                if (__builtin_popcount(sub) & 1) res -= g[sub | mask2];
                else res += g[sub | mask2];
            }
        } else if (d2 <= 6) {
            res = (d2 & 1) ? -f[mask3] : f[mask3];
            for (int sub = mask2; sub > 0; sub = (sub - 1) & mask2) {
                if (__builtin_popcount(sub ^ mask2) & 1) res -= f[sub | mask3];
                else res += f[sub | mask3];
            }
        } else {
            res = a[mask2];
            for (int sub = mask3; sub > 0; sub = (sub - 1) & mask3) {
                res += a[sub | mask2];
            }
        }
        cout << res << "\n";
    }
}

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

    #define file ""
    if (fopen(file ".inp", "r")) {
        freopen(file ".inp", "r", stdin);
        freopen(file ".out", "w", stdout);
    }

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

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

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