Submission #1362347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1362347		dex111222333444555	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	369 ms	20688 KiB

snake_escaping

#include <bits/stdc++.h>
#include <chrono>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define lli pair<long long, int>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define bcnt(x) __builtin_popcount(x)

using namespace std;

const int infINT = 1e9 + 123;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

#define ll long long
ll ran(ll l, ll r){
    assert(l <= r);
    return uniform_int_distribution<ll>(l, r)(rd);
}

const int MAXN = 20;

int lenS, numQuery, val[MASK(MAXN)];
int f[MASK(MAXN)], g[MASK(MAXN)];

void input(){
    cin >> lenS >> numQuery;

    for(int i = 0; i < MASK(lenS); i++){
        char c; cin >> c;
        val[i] = (c - '0');
        f[i] = g[i] = val[i];
    }

}

string binary(const int &mask){
    string s = "";
    for(int i = lenS - 1; i >= 0; i--) s += (BIT(mask, i) + '0');
    return s;
}

void solve(){
    for(int i = 0; i < lenS; i++){
        for(int mask = 0; mask < MASK(lenS); mask++){
            if (BIT(mask, i)){
                f[mask] += f[mask ^ MASK(i)];
            }else{
                g[mask] += g[mask ^ MASK(i)];
            }
        }
    }

    for(int q = 1; q <= numQuery; q++){

        string query; cin >> query;
        reverse(all(query));

        int numA = 0, numB = 0, numC = 0, A = 0, B = 0, C = 0;

        for(int i = 0; i < lenS; i++){
            if (query[i] == '0'){
                numA++;
                A |= MASK(i);
            }else if (query[i] == '1'){
                numB++;
                B |= MASK(i);
            }else{
                numC++;
                C |= MASK(i);
            }
        }

        long long res = 0;

        if (numA <= min(numB, numC)){
            for(int submask = A; 1; submask = (submask - 1) & A){
                res += 1LL * g[submask | B] * 1LL * (bcnt(submask) % 2 ? -1: +1);
                if (submask == 0) break;
            }
        }

        else if (numB <= min(numA, numC)){
            for(int submask = B; 1; submask = (submask - 1) & B){
                res += 1LL * f[submask | C] * 1LL * (bcnt(B) % 2 == bcnt(submask) % 2 ? +1: -1);
                if (submask == 0) break;
            }
        }

        else if (numC <= min(numA, numB)){
            for(int submask = C; 1; submask = (submask - 1) & C){
                res += val[submask | B];
                if (submask == 0) break;
            }
        }

        cout << res << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    input();
    solve();
    cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}

Compilation message (stderr)

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

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