oj.uz

Submission #990210

# Submission time Handle Problem Language Result Execution time Memory
990210 2024-05-29T21:45:59 Z AlphaMale06 Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 18448 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 21;

int val[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';
    }
    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;
        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][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][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][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][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++){
      |                  ~^~~~~~~~~
snake_escaping.cpp:40:13: warning: unused variable 'mn' [-Wunused-variable]
   40 |         int mn  = min({cntu, cnt1, cnt0});
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 329 ms 17176 KB Output is correct
12 Correct 673 ms 16768 KB Output is correct
13 Correct 222 ms 16208 KB Output is correct
14 Correct 237 ms 16056 KB Output is correct
15 Correct 504 ms 17128 KB Output is correct
16 Correct 308 ms 16464 KB Output is correct
17 Correct 372 ms 16212 KB Output is correct
18 Execution timed out 2025 ms 6100 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 329 ms 17176 KB Output is correct
12 Correct 673 ms 16768 KB Output is correct
13 Correct 222 ms 16208 KB Output is correct
14 Correct 237 ms 16056 KB Output is correct
15 Correct 504 ms 17128 KB Output is correct
16 Correct 308 ms 16464 KB Output is correct
17 Correct 372 ms 16212 KB Output is correct
18 Execution timed out 2025 ms 6100 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 539 ms 18448 KB Output is correct
12 Execution timed out 2045 ms 17652 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 11 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 329 ms 17176 KB Output is correct
12 Correct 673 ms 16768 KB Output is correct
13 Correct 222 ms 16208 KB Output is correct
14 Correct 237 ms 16056 KB Output is correct
15 Correct 504 ms 17128 KB Output is correct
16 Correct 308 ms 16464 KB Output is correct
17 Correct 372 ms 16212 KB Output is correct
18 Execution timed out 2025 ms 6100 KB Time limit exceeded
19 Halted 0 ms 0 KB -