Submission #1137007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137007		onlk97	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1140 ms	32912 KiB

snake_escaping

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
using tii=pair <pii,int>;
void solve(){
    int n,q;
    cin>>n>>q;
    int a[1<<n];
    for (int i=0; i<(1<<n); i++){
        char c; cin>>c;
        a[i]=(c-'0');
    }
    int s[1<<n],rs[1<<n];
    for (int i=0; i<(1<<n); i++) s[i]=rs[i]=a[i];
    for (int b=0; b<n; b++){
        for (int i=0; i<(1<<n); i++){
            if (i&(1<<b)) s[i]+=s[i^(1<<b)];
        }
    }
    for (int b=0; b<n; b++){
        for (int i=(1<<n)-1; i>=0; i--){
            if (!(i&(1<<b))) rs[i]+=rs[i^(1<<b)];
        }
    }
    while (q--){
        string str; cin>>str;
        vector <int> f[3];
        for (int i=0; i<n; i++){
            if (str[i]=='0') f[0].pb(n-1-i);
            else if (str[i]=='1') f[1].pb(n-1-i);
            else f[2].pb(n-1-i);
        }
        int sz[3]={f[0].size(),f[1].size(),f[2].size()};
        int ans=0,ths=0;
        for (int i:f[1]) ths+=(1<<i);
        if (sz[2]<=min(sz[0],sz[1])){
            for (int mask=0; mask<(1<<sz[2]); mask++){
                int tp=ths;
                for (int j=0; j<sz[2]; j++){
                    if (mask&(1<<j)) tp+=(1<<f[2][j]);
                }
                ans+=a[tp];
            }
        } else if (sz[1]<=min(sz[0],sz[2])){
            for (int i:f[2]) ths+=(1<<i);
            for (int mask=0; mask<(1<<sz[1]); mask++){
                int tp=ths,sn=0;
                for (int j=0; j<sz[1]; j++){
                    if (mask&(1<<j)){
                        tp-=(1<<f[1][j]);
                        sn^=1;
                    }
                }
                ans+=s[tp]*(sn==0?1:-1);
            }
        } else {
            for (int mask=0; mask<(1<<sz[0]); mask++){
                int tp=ths,sn=0;
                for (int j=0; j<sz[0]; j++){
                    if (mask&(1<<j)){
                        tp+=(1<<f[0][j]);
                        sn^=1;
                    }
                }
                ans+=rs[tp]*(sn==0?1:-1);
            }
        }
        cout<<ans<<'\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
}

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:41:29: warning: narrowing conversion of 'f[0].std::vector<long long int>::size()' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   41 |         int sz[3]={f[0].size(),f[1].size(),f[2].size()};
      |                    ~~~~~~~~~^~
snake_escaping.cpp:41:41: warning: narrowing conversion of 'f[1].std::vector<long long int>::size()' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   41 |         int sz[3]={f[0].size(),f[1].size(),f[2].size()};
      |                                ~~~~~~~~~^~
snake_escaping.cpp:41:53: warning: narrowing conversion of 'f[2].std::vector<long long int>::size()' from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
   41 |         int sz[3]={f[0].size(),f[1].size(),f[2].size()};
      |                                            ~~~~~~~~~^~

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