Submission #990233

#	Time	Username	Problem	Language	Result	Execution time	Memory
990233		AlphaMale06	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	543 ms	51708 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int N = 21;

int val[1<<N], ppcnt[1<<N];
int dp[1<<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]=dp[i][1]=s[i]-'0';
        ppcnt[i]=__builtin_popcount(i);
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<(1<<n); j++){
            if(j & (1<<(i-1))){
                dp[j][0]+=dp[j^(1<<(i-1))][0];
            }
            else{
                dp[j][1]+=dp[j^(1<<(i-1))][1];
            }
        }
    }
    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, mask1 = 0;
        if(cntu == mn){
            for(int i=0; i< n; i++){
                if(qry[i]=='1')mask+=1<<(n-i-1);
                else if(qry[i]=='?')mask1+=1<<(n-i-1);
            }
            for(int m = mask1; ; m=(m-1)&mask1){
                ans+=val[mask|m];
                if(!m)break;
            }
            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')mask1+=1<<(n-i-1);
            }
            int pcnt = ppcnt[mask1|mask]&1;
            for(int m = mask1; ; m=(m-1)&mask1){
                if((ppcnt[m|mask]&1)^pcnt)ans-=dp[m|mask][1];
                else ans+=dp[m|mask][1];
                if(!m)break;
            }
            cout << abs(ans) << '\n';
        }
        else{
            for(int i=0; i< n; i++){
                if(qry[i]=='?')mask+=1<<(n-i-1);
                else if(qry[i]=='1')mask1+=1<<(n-i-1);
            }
            int pcnt = ppcnt[mask1|mask]&1;
            for(int m = mask1; ; m=(m-1)&mask1){
                if((ppcnt[m|mask]&1)^pcnt)ans-=dp[m|mask][0];
                else ans+=dp[m|mask][0];
                if(!m)break;
            }
            cout << abs(ans) << '\n';
        }
    }
}

Compilation message (stderr)

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

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