Submission #966951

#	Time	Username	Problem	Language	Result	Execution time	Memory
966951		efedmrlr	Snake Escaping (JOI18_snake_escaping)	C++17	12 / 100	2027 ms	26704 KiB

snake_escaping

// #pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
    
using namespace std;
    
    
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
    
    
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
    
    
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,q;
vector<int> dp, dpr, a;
int RVSR;
inline void solve() {
    cin>>n>>q;
    dp.assign((1 << n), 0);
    dpr.assign((1 << n), 0);
    a.assign((1 << n), 0);
    RVSR = (1 << n) - 1;
    for(int i = 0; i < (1 << n); i++) {
        char tmp;
        cin >> tmp;
        a[i] = dp[i] = dpr[i ^ RVSR] = tmp - '0';
    }
    
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < (1 << n); i++) {
            if(i & (1 << k)) {
                dp[i] += dp[i ^ (1 << k)];
                dpr[i] += dpr[i ^ (1 << k)];
            }
        }
    }
    // for(int i = 0; i < (1 << n); i++) {
    //     cout << "i:" << i <<" dp:" << dp[i] << " dpr:" << dpr[i] << "\n";
    // }
    REP(z, q) {
        string s;
        cin >> s;
        reverse(all(s));
        int cnt0 = 0, cnt1 = 0;
        for(char c : s) {
            if(c == '0') cnt0++;
            else if(c == '1') cnt1++;
        }
        int ans = 0;
        if(cnt1 + cnt0 >= 14) {
            int x = 0;
            vector<int> occ;
            for(int i = 0; i < n; i++) {
                if(s[i] == '?') occ.pb(i);
                if(s[i] == '1') x += (1 << i);
            }
            for(int mask = 0; mask < (1 << occ.size()); mask++) {
                for(int i = 0; i < occ.size(); i++) {
                    if(mask & (1 << i)) {
                        x += (1 << occ[i]);
                    }
                }
                ans += a[x];
            }
        }
        else if(cnt1 > cnt0) {   // use reverse
            int x = 0;
            vector<int> occ;
            for(int i = 0; i < n; i++) {
                if(s[i] != '1') x += (1 << i);
                if(s[i] == '0') {
                    occ.pb(i);
                }
            }
            for(int mask = 0; mask < (1 << ((int)occ.size())); mask++) {
                int cur = x;
                for(int i = 0; i < occ.size(); i++) {
                    if(mask & (1 << i)) {
                        cur ^= 1 << (occ[i]);
                    }
                }
                if(__popcount(mask) & 1) {
                    ans -= dpr[cur];
                }
                else {
                    ans += dpr[cur];
                }
            }
        }
        else {
            int x = 0;
            vector<int> occ;
            for(int i = 0; i < n; i++) {
                if(s[i] != '0') x += (1 << i);
                if(s[i] == '1') {
                    occ.pb(i);
                }
            }
            for(int mask = 0; mask < (1 << ((int)occ.size())); mask++) {
                int cur = x;
                // cout << "mask:" << mask << " cur:" << cur << "\n";
                for(int i = 0; i < occ.size(); i++) {
                    if(mask & (1 << i)) {
                        cur ^= 1 << (occ[i]);
                    }
                }
                if(__popcount(mask) & 1) {
                    ans -= dp[cur];
                }
                else {
                    ans += dp[cur];
                }
            }
        }
        cout << ans << endl;
    }
    
    
    
}
    
signed main() {
    
    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:72:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 for(int i = 0; i < occ.size(); i++) {
      |                                ~~^~~~~~~~~~~~
snake_escaping.cpp:91:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 for(int i = 0; i < occ.size(); i++) {
      |                                ~~^~~~~~~~~~~~
snake_escaping.cpp:116:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 for(int i = 0; i < occ.size(); i++) {
      |                                ~~^~~~~~~~~~~~

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