Submission #857785

#	Time	Username	Problem	Language	Result	Execution time	Memory
857785		TS_2392	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	788 ms	58752 KiB

snake_escaping

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
// using namespace __gnu_pbds;

#define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED         ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL            cout << '\n'
#define dbg(x)        cout << #x << " = " << (x) << ' '
#define dbgp(x)       cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}

#define epl           emplace
#define pb            push_back
#define eb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair

#define sqr(x)        ((x) * (x))
#define all(x)        (x).begin(), (x).end()
#define rall(x)       (x).rbegin(), (x).rend()
#define lwb           lower_bound
#define upb           upper_bound

#define clz           __builtin_clzll // or __builtin_clz
#define ctz           __builtin_ctzll // or __builtin_ctz
#define pct           __builtin_popcountll // or __builtin_popcount

typedef long long            ll;
typedef long double          ldb;
typedef unsigned int         uint;
typedef unsigned long long   ull;
typedef pair<ll, ll>         pll;
typedef pair<ll, int>        pli;
typedef pair<int, ll>        pil;
typedef pair<int, int>       pii;
typedef pair<ldb, ldb>       pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
template<class T> void remDup(vector<T> &v){sort(all(v)); v.erase(unique(all(v)),v.end());}

// int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int N = 20, Q = 1e6 + 3;
int n, q, sz[1 << N];
ll dp1[1 << N], dp2[1 << N], a[1 << N];
void TS_2392(){
    cin >> n >> q;
    for(int i = 0; i < (1 << n); ++i){
        char c; cin >> c;
        sz[i] = pct(i);
        dp1[i] = dp2[i] = a[i] = c - '0';
    }
    for(int i = 0; i < n; ++i){
        for(int mask = 0; mask < 1 << n; ++ mask){
            if(mask >> i & 1){
                dp1[mask] += dp1[mask ^ (1 << i)];
            }
            else{
                dp2[mask] += dp2[mask ^ (1 << i)];
            }
        }
    }
    while(q--){
        string s; cin >> s; reverse(all(s));
        int cnt0 = 0, cnt1 = 0, cnt_qm = 0;
        for(int i = 0; i < n; ++i){
            if(s[i] == '0') ++cnt0;
            if(s[i] == '1') ++cnt1;
            if(s[i] == '?') ++cnt_qm;
        }
        //dbg(s); EL;
        if(cnt0 <= 6){
            int mask1 = 0, mask2 = 0;
            for(int i = 0; i < n; ++i){
                if(s[i] == '1') mask1 ^= 1 << i;
                if(s[i] == '0') mask2 ^= 1 << i;
            }
            //dbg(bitset<4>(mask1)); EL;
            //dbg(bitset<4>(mask2)); EL;
            ll res = 0;
            for(int x = mask2, i = 1; i <= (1 << sz[mask2]); x = (x - 1) & mask2, ++i){
                int cur = (x ^ mask2);
                //dbg(mask1 ^ cur); dbg(dp2[mask1 ^ cur]); EL;
                if(sz[cur] & 1) res -= dp2[mask1 ^ cur];
                else res += dp2[mask1 ^ cur];
            }
            cout << res << '\n';
        }
        else if(cnt1 <= 6){
            int mask1 = 0, mask2 = 0;
            for(int i = 0; i < n; ++i){
                if(s[i] == '?') mask1 ^= 1 << i;
                if(s[i] == '1') mask2 ^= 1 << i, mask1 ^= 1 << i;
            }
            ll res = 0;
            for(int x = mask2, i = 1; i <= (1 << sz[mask2]); x = (x - 1) & mask2, ++i){
                int cur = x;
                if(sz[mask2 ^ cur] & 1) res -= dp1[mask1 ^ mask2 ^ cur];
                else res += dp1[mask1 ^ mask2 ^ cur];
            }
            cout << res << '\n';
        }
        else{
            int mask1 = 0, mask2 = 0;
            for(int i = 0; i < n; ++i){
                if(s[i] == '1') mask1 ^= 1 << i;
                if(s[i] == '?') mask2 ^= 1 << i;
            }
            ll res = 0;
            for(int x = mask2, i = 1; i <= (1 << sz[mask2]); x = (x - 1) & mask2, ++i){
                res += a[mask1 ^ x];
            }
            cout << res << '\n';
        }
    }
}
int main(){
    SPEED; fileIO("text");
    int numtest = 1; //cin >> numtest;
    for(int itest = 1; itest <= numtest; ++itest){
        // cout << "Case #" << itest << ": ";
        TS_2392();
    }
    return 0;
}
/* stuff you should look for
 * keep calm, don't panic
 * int overflow, array bounds
 * small cases, special cases (n = 1, 2 x 2 matrix, tree with n - 1 leafs, ...)
 * GUESS, fix something, lower bound or upper bound for the problem
 * do something instead of nothing: code bruteforce, ...
 * WRITE STUFF DOWN and STAY ORGANIZED
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:127:12: note: in expansion of macro 'fileIO'
  127 |     SPEED; fileIO("text");
      |            ^~~~~~
snake_escaping.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:127:12: note: in expansion of macro 'fileIO'
  127 |     SPEED; fileIO("text");
      |            ^~~~~~

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