oj.uz

Submission #990201

# Submission time Handle Problem Language Result Execution time Memory
990201 2024-05-29T21:19:45 Z AlphaMale06 Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 7 ms 4956 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Runtime error 7 ms 4956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Runtime error 7 ms 4956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Runtime error 7 ms 4956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Runtime error 7 ms 4956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Runtime error 7 ms 4956 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -