Submission #966955

#	Time	Username	Problem	Language	Result	Execution time	Memory
966955		efedmrlr	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2032 ms	25204 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;
    int RVSR;
    inline void solve() {
        cin>>n>>q;
        dp.assign((1 << n), 0);
        dpr.assign((1 << n), 0);
        RVSR = (1 << n) - 1;
        for(int i = 0; i < (1 << n); i++) {
            char tmp;
            cin >> tmp;
            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) {   // 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:74:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                     for(int i = 0; i < occ.size(); i++) {
      |                                    ~~^~~~~~~~~~~~
snake_escaping.cpp:99:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                     for(int i = 0; i < occ.size(); i++) {
      |                                    ~~^~~~~~~~~~~~

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