oj.uz

Submission #949613

# Submission time Handle Problem Language Result Execution time Memory
949613 2024-03-19T12:32:37 Z ace5 Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 742 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 21;
const int maxsz = 1<<21;

int x[maxsz];
int sos[maxsz];
int soo[maxsz];
int dp[maxn][maxsz];

int recq(int sv,int tpos,vector<int>& posq)
{
    if(tpos == posq.size())
    {
        return x[sv];
    }
    else
    {
        return recq(sv,tpos+1,posq) + recq(sv+(1<<posq[tpos]),tpos+1,posq);
    }
}
int rec0(int sv,int c0,int tpos,vector<int>& posq)
{
    if(tpos == posq.size())
    {
        return (c0%2 == 0 ? 1 : -1)*sos[sv];
    }
    else
    {
        return rec0(sv,c0+1,tpos+1,posq) + rec0(sv+(1<<posq[tpos]),c0,tpos+1,posq);
    }
}
int rec1(int sv,int c1,int tpos,vector<int>& posq)
{
    if(tpos == posq.size())
    {
        return (c1%2 == 0 ? 1 : -1)*soo[sv];
    }
    else
    {
        return rec1(sv,c1,tpos+1,posq) + rec1(sv+(1<<posq[tpos]),c1+1,tpos+1,posq);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    int sz = 1<<n;
    for(int j = 0;j < sz;++j)
    {
        char c;
        cin >> c;
        x[j] = c-'0';
    }
    for(int i = 0;i <= n;++i)
    {
        for(int j = 0;j < sz;++j)
        {
            if(i == 0)
            {
                dp[i][j] = x[j];
            }
            else
            {
                dp[i][j] = ((j&(1<<(i-1))) == 0 ? dp[i-1][j] : dp[i-1][j] + dp[i-1][j^(1<<(i-1))]);
            }
        }
    }
    for(int i = 0;i < sz;++i)
    {
        sos[i] = dp[n][i];
    }
    for(int i = 0;i <= n;++i)
    {
        for(int j = 0;j < sz;++j)
        {
            if(i == 0)
            {
                dp[i][j] = x[j];
            }
            else
            {
                dp[i][j] = ((j&(1<<(i-1))) != 0 ? dp[i-1][j] : dp[i-1][j] + dp[i-1][j^(1<<(i-1))]);
            }
        }
    }
    for(int i = 0;i < sz;++i)
    {
        soo[i] = dp[n][i];
    }
    while(q--)
    {
        vector<char> c(n);
        int c0 = 0,c1 = 0,cq = 0;
        for(int j = 0;j < n;++j)
        {
            cin >> c[j];
            if(c[j] == '?')
                cq++;
            else if(c[j] == '0')
                c0++;
            else
                c1++;
        }
        if(cq <= 6)
        {
            int sv = 0;
            vector<int> posq;
            for(int j = 0;j < n;++j)
            {
                if(c[j] == '?')
                    posq.push_back(n-j-1);
                sv*=2;
                sv += (c[j] == '1' ? 1 : 0);
            }
            cout << recq(sv,0,posq) << "\n";
        }
        else if(c0 <= 6)
        {
            int sv = 0;
            vector<int> pos0;
            for(int j = 0;j < n;++j)
            {
                if(c[j] == '0')
                    pos0.push_back(n-j-1);
                sv*=2;
                sv += (c[j] == '1' ? 1 : 0);
            }
            cout << rec1(sv,0,0,pos0) << "\n";
        }
        else
        {
            int sv = 0;
            vector<int> pos1;
            for(int j = 0;j < n;++j)
            {
                if(c[j] == '1')
                    pos1.push_back(n-j-1);
                sv*=2;
                sv += (c[j] == '?' ? 1 : 0);
            }
            cout << rec0(sv,0,0,pos1) << "\n";
        }
    }
}

Compilation message

snake_escaping.cpp: In function 'int recq(int, int, std::vector<int>&)':
snake_escaping.cpp:15:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if(tpos == posq.size())
      |        ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp: In function 'int rec0(int, int, int, std::vector<int>&)':
snake_escaping.cpp:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(tpos == posq.size())
      |        ~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp: In function 'int rec1(int, int, int, std::vector<int>&)':
snake_escaping.cpp:37:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(tpos == posq.size())
      |        ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 4 ms 26968 KB Output is correct
11 Correct 495 ms 31140 KB Output is correct
12 Correct 482 ms 30804 KB Output is correct
13 Correct 369 ms 30036 KB Output is correct
14 Correct 342 ms 30092 KB Output is correct
15 Correct 662 ms 30924 KB Output is correct
16 Correct 458 ms 30292 KB Output is correct
17 Correct 393 ms 30228 KB Output is correct
18 Correct 211 ms 32108 KB Output is correct
19 Correct 196 ms 29120 KB Output is correct
20 Correct 471 ms 30696 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 4 ms 26968 KB Output is correct
11 Correct 495 ms 31140 KB Output is correct
12 Correct 482 ms 30804 KB Output is correct
13 Correct 369 ms 30036 KB Output is correct
14 Correct 342 ms 30092 KB Output is correct
15 Correct 662 ms 30924 KB Output is correct
16 Correct 458 ms 30292 KB Output is correct
17 Correct 393 ms 30228 KB Output is correct
18 Correct 211 ms 32108 KB Output is correct
19 Correct 196 ms 29120 KB Output is correct
20 Correct 471 ms 30696 KB Output is correct
21 Correct 320 ms 37164 KB Output is correct
22 Correct 623 ms 37484 KB Output is correct
23 Correct 440 ms 36360 KB Output is correct
24 Correct 450 ms 36256 KB Output is correct
25 Correct 448 ms 38332 KB Output is correct
26 Correct 525 ms 36616 KB Output is correct
27 Correct 494 ms 36544 KB Output is correct
28 Correct 255 ms 39272 KB Output is correct
29 Correct 219 ms 35184 KB Output is correct
30 Correct 503 ms 37272 KB Output is correct
31 Correct 742 ms 37200 KB Output is correct
32 Correct 586 ms 37576 KB Output is correct
33 Correct 385 ms 36148 KB Output is correct
34 Correct 445 ms 36324 KB Output is correct
35 Correct 517 ms 36684 KB Output is correct
36 Correct 235 ms 35348 KB Output is correct
37 Correct 679 ms 37316 KB Output is correct
38 Correct 234 ms 35156 KB Output is correct
39 Correct 442 ms 36352 KB Output is correct
40 Correct 442 ms 36172 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 4 ms 26968 KB Output is correct
11 Runtime error 34 ms 65536 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26968 KB Output is correct
2 Correct 4 ms 26972 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 4 ms 26972 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 4 ms 26968 KB Output is correct
11 Correct 495 ms 31140 KB Output is correct
12 Correct 482 ms 30804 KB Output is correct
13 Correct 369 ms 30036 KB Output is correct
14 Correct 342 ms 30092 KB Output is correct
15 Correct 662 ms 30924 KB Output is correct
16 Correct 458 ms 30292 KB Output is correct
17 Correct 393 ms 30228 KB Output is correct
18 Correct 211 ms 32108 KB Output is correct
19 Correct 196 ms 29120 KB Output is correct
20 Correct 471 ms 30696 KB Output is correct
21 Correct 320 ms 37164 KB Output is correct
22 Correct 623 ms 37484 KB Output is correct
23 Correct 440 ms 36360 KB Output is correct
24 Correct 450 ms 36256 KB Output is correct
25 Correct 448 ms 38332 KB Output is correct
26 Correct 525 ms 36616 KB Output is correct
27 Correct 494 ms 36544 KB Output is correct
28 Correct 255 ms 39272 KB Output is correct
29 Correct 219 ms 35184 KB Output is correct
30 Correct 503 ms 37272 KB Output is correct
31 Correct 742 ms 37200 KB Output is correct
32 Correct 586 ms 37576 KB Output is correct
33 Correct 385 ms 36148 KB Output is correct
34 Correct 445 ms 36324 KB Output is correct
35 Correct 517 ms 36684 KB Output is correct
36 Correct 235 ms 35348 KB Output is correct
37 Correct 679 ms 37316 KB Output is correct
38 Correct 234 ms 35156 KB Output is correct
39 Correct 442 ms 36352 KB Output is correct
40 Correct 442 ms 36172 KB Output is correct
41 Runtime error 34 ms 65536 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -