Submission #1298038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298038		mohammadsam	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	374 ms	17760 KiB

snake_escaping

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 20,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , q;
string s;
string s2;
int sub[1<<N],over[1<<N];
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n >> q >> s;
    for(int mask = 0;mask < (1<<n);mask++){
        sub[mask] = over[mask] = (s[mask] - '0');
    }
    for(int i = 0;i<n;i++){
        for(int mask = 0;mask < (1<<n);mask++){
            if(mask&(1<<i)) sub[mask] += sub[mask^(1<<i)];
        }
    }
    for(int i = 0 ; i < n;i++){
        for(int mask = 0;mask < (1<<n);mask++){
            if((mask&(1<<i)) == 0) over[mask] += over[mask^(1<<i)];
        }
    }
    while(q--){
        cin >> s2;
        int mark=0,yek=0,sefr = 0;
        for(int i = 0 ;i < n;i++){
            if(s2[i] == '?') mark ^= (1<<(n - 1 - i));
            else if(s2[i] == '0') sefr ^= (1<<(n - 1- i));
            else yek ^= (1<<( n - 1 - i));
        }
        if(popcount(mark) <= 6){
            int ans = 0;
            for(int m = mark;;m = ((m-1)&mark)){
                ans += (s[m + yek] - '0');
                if(m == 0) break;
            }
            cout << ans << endl;
            continue;
        }
        if(popcount(yek) <= 6){
            int ans = 0;
            for(int m = yek;; m = ((m-1)&yek)){
                if((popcount(m)&1) == (popcount(yek)&1)) ans += sub[m + mark];
                else ans -= sub[m + mark];
                if(m == 0) break;
            }
            cout << ans << endl;
            continue;
        }
        int ans = 0;
        for(int m = sefr;;m = ((m-1)&sefr)){
            if(popcount(m)&1) ans -= over[m + yek];
            else ans += over[m + yek];
            if(m == 0) break;
        }
        cout << ans << endl;
    }
    return 0;
}

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