Submission #990201

#	Time	Username	Problem	Language	Result	Execution time	Memory
990201		AlphaMale06	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	7 ms	4956 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int N = 21;

int val[1<<N];
int dp[1<<N][N][2];
//0 je za ?1, 1 je za ?0
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    for(int i=0; i<s.size(); i++){
        val[i]=dp[i][0][0]=dp[i][0][1]=s[i]-'0';
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<(1<<n); j++){
            if(j & (1<<(i-1))){
                dp[j][i][0]=dp[j][i-1][0]+dp[j^(1<<(i-1))][i-1][0];
                dp[j][i][1]=dp[j][i-1][1];
            }
            else{
                dp[j][i][1]=dp[j][i-1][1]+dp[j^(1<<(i-1))][i-1][1];
                dp[j][i][0]=dp[j][i-1][0];
            }
        }
    }
    while(q--){
        string qry;
        cin >> qry;
        int cntu=0, cnt1=0, cnt0=0;
        for(char c : qry){
            if(c=='?')cntu++;
            else if(c=='1')cnt1++;
            else cnt0++;
        }
        int mn  = min({cntu, cnt1, cnt0});
        int ans=0;
        int mask = 0;
        vector<int> pos;
        if(cntu == mn){
            for(int i=0; i< n; i++){
                if(qry[i]=='1')mask+=1<<(n-i-1);
                else if(qry[i]=='?')pos.push_back(n-1-i);
            }
            for(int i=0; i< (1<<cntu); i++){
                int mask1=mask;
                for(int j=0; j<cntu; j++){
                    if(i & (1<<j)){
                        mask1+=1<<pos[j];
                    }
                }
                ans+=val[mask1];
            }
            cout << ans << '\n';
        }
        else if(cnt0 == mn){
            for(int i=0; i< n; i++){
                if(qry[i]=='1')mask+=1<<(n-i-1);
                else if(qry[i]=='0')pos.push_back(n-1-i);
            }
            ans = dp[mask][n][1];

            for(int i=1; i< (1<<cnt0); i++){
                int mask1=mask;
                for(int j=0; j<cnt0; j++){
                    if(i & (1<<j)){
                        mask1+=1<<pos[j];
                    }
                }
                ans-=dp[mask1][n][1];
            }
            cout << ans << '\n';
        }
        else{
            for(int i=0; i< n; i++){
                if(qry[i]=='?')mask+=1<<(n-i-1);
                else if(qry[i]=='1')pos.push_back(n-1-i);
            }
            ans = dp[mask][n][0];
            for(int i=1; i< (1<<cnt1); i++){
                int mask1=0;
                for(int j=0; j<cnt1; j++){
                    if(i&(1<<j))mask1+=1<<pos[j];
                }
                ans-=dp[mask-mask1][n][0];
            }
            cout << ans << '\n';
        }
    }
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~

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