oj.uz

Submission #1117514

# Submission time Handle Problem Language Result Execution time Memory
1117514 2024-11-23T20:42:28 Z Szymon_Pilipczuk Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1329 ms 50360 KB 
#include <bits/stdc++.h>
using namespace std;
int pot[21];
int tox[1048576];
long long dp1[1048576];
long long dp0[1048576];
int c[3];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pot[0] = 1;
    for(int i = 1;i<=20;i++) pot[i] = 2*pot[i-1];
    int l,q;
    cin>>l>>q;
    for(int i = 0;i<pot[l];i++)
    {
        char c;
        cin>>c;
        tox[i] = int(c)-48;
        dp1[i] = tox[i];
        dp0[i] = tox[i];
        //cout<<dp1[i]<<"   "<<i<<"\n";
    }
    for(int i = 0;i<l;i++)
    {
        for(int j = 0;j<pot[l];j++)
        {
            if(j & pot[i])
            {
                dp1[j] += dp1[j-pot[i]];
            }
            //cout<<dp1[j]<<" "<<i+1<<" "<<j<<"\n";
        }
    }
    for(int i = 0;i<l;i++)
    {
        for(int j = 0;j<pot[l];j++)
        {
            if(!(j&pot[i]))
            {
                dp0[j] += dp0[j+pot[i]];
            }
        }
    }

    for(int w = 0;w<q;w++)
    {
        int ans = 0;
        int p[l];
        vector<int>cpl;
        vector<int>c0l;
        vector<int>c1l;
        int lq = 0;
        int l1 = 0;
        int l0 = 0;
        for(int j = l-1;j>=0;j--)
        {
            char c;
            cin>>c;
            if(c == '?')
            {
                p[j] = 2;
                l1+=pot[j];
                cpl.push_back(j);
            }
            else
            {
                p[j] = int(c)-48;
                if(p[j] == 0)
                {
                    c0l.push_back(j);
                }
                else
                {
                    lq+=pot[j];
                    l1+=pot[j];
                    l0+=pot[j];
                    c1l.push_back(j);
                }
            }
        }

        if(min(min(c0l.size(),c1l.size()),cpl.size()) == cpl.size())
        {
            for(int i = 0;i<pot[cpl.size()];i++)
            {
                int l2 = lq;
                for(int j = 0;j<cpl.size();j++)
                {
                    if(i & pot[j])
                    {
                        l2+= pot[cpl[j]];
                    }
                }
                ans += tox[l2];
            }
        }
        else if(min(c0l.size(),c1l.size()) == c1l.size())
        {
            for(int i = 0;i<pot[c1l.size()];i++)
            {
                int l2 = l1;
                int c = c1l.size()%2;
                for(int j = 0;j<c1l.size();j++)
                {
                    if(i & pot[j])
                    {
                        l2-=pot[c1l[j]];
                        c = c^1;
                    }
                }
                if(c == 0) ans+=dp1[l2];
                else ans-=dp1[l2];
            }
        }
        else
        {
            for(int i = 0;i<pot[c0l.size()];i++)
            {
                int l2 = l0;
                int c = c0l.size()%2;
                for(int j = 0;j<c0l.size();j++)
                {
                    if(i&pot[j])
                    {
                        l2+=pot[c0l[j]];
                        c = c^1;
                    }
                }
                if(c == 0) ans+=dp0[l2];
                else ans-=dp0[l2];

            }
        }
        cout<<abs(ans)<<"\n";

    }

}

Compilation message

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:90:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |                 for(int j = 0;j<cpl.size();j++)
      |                               ~^~~~~~~~~~~
snake_escaping.cpp:106:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 for(int j = 0;j<c1l.size();j++)
      |                               ~^~~~~~~~~~~
snake_escaping.cpp:124:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |                 for(int j = 0;j<c0l.size();j++)
      |                               ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4596 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4600 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 358 ms 19192 KB Output is correct
12 Correct 347 ms 19016 KB Output is correct
13 Correct 390 ms 18076 KB Output is correct
14 Correct 402 ms 18248 KB Output is correct
15 Correct 385 ms 19272 KB Output is correct
16 Correct 465 ms 18328 KB Output is correct
17 Correct 428 ms 18248 KB Output is correct
18 Correct 233 ms 20208 KB Output is correct
19 Correct 356 ms 17224 KB Output is correct
20 Correct 350 ms 19016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4596 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4600 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 358 ms 19192 KB Output is correct
12 Correct 347 ms 19016 KB Output is correct
13 Correct 390 ms 18076 KB Output is correct
14 Correct 402 ms 18248 KB Output is correct
15 Correct 385 ms 19272 KB Output is correct
16 Correct 465 ms 18328 KB Output is correct
17 Correct 428 ms 18248 KB Output is correct
18 Correct 233 ms 20208 KB Output is correct
19 Correct 356 ms 17224 KB Output is correct
20 Correct 350 ms 19016 KB Output is correct
21 Correct 434 ms 22344 KB Output is correct
22 Correct 436 ms 22344 KB Output is correct
23 Correct 493 ms 21492 KB Output is correct
24 Correct 574 ms 21320 KB Output is correct
25 Correct 460 ms 23244 KB Output is correct
26 Correct 548 ms 21620 KB Output is correct
27 Correct 569 ms 21576 KB Output is correct
28 Correct 266 ms 24136 KB Output is correct
29 Correct 412 ms 20200 KB Output is correct
30 Correct 431 ms 22344 KB Output is correct
31 Correct 523 ms 22064 KB Output is correct
32 Correct 595 ms 22108 KB Output is correct
33 Correct 466 ms 21072 KB Output is correct
34 Correct 573 ms 20812 KB Output is correct
35 Correct 571 ms 21704 KB Output is correct
36 Correct 281 ms 20560 KB Output is correct
37 Correct 412 ms 22280 KB Output is correct
38 Correct 441 ms 20324 KB Output is correct
39 Correct 516 ms 21400 KB Output is correct
40 Correct 578 ms 21140 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4596 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4600 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 103 ms 23256 KB Output is correct
12 Correct 77 ms 23112 KB Output is correct
13 Correct 91 ms 23128 KB Output is correct
14 Correct 108 ms 22856 KB Output is correct
15 Correct 76 ms 23120 KB Output is correct
16 Correct 134 ms 23112 KB Output is correct
17 Correct 99 ms 23116 KB Output is correct
18 Correct 60 ms 23252 KB Output is correct
19 Correct 73 ms 22856 KB Output is correct
20 Correct 75 ms 23120 KB Output is correct
21 Correct 91 ms 23052 KB Output is correct
22 Correct 98 ms 23112 KB Output is correct
23 Correct 77 ms 22992 KB Output is correct
24 Correct 104 ms 23112 KB Output is correct
25 Correct 102 ms 22888 KB Output is correct
26 Correct 60 ms 23112 KB Output is correct
27 Correct 95 ms 23052 KB Output is correct
28 Correct 75 ms 23004 KB Output is correct
29 Correct 84 ms 23112 KB Output is correct
30 Correct 105 ms 23112 KB Output is correct
31 Correct 77 ms 23128 KB Output is correct
32 Correct 107 ms 23000 KB Output is correct
33 Correct 107 ms 23000 KB Output is correct
34 Correct 59 ms 23112 KB Output is correct
35 Correct 99 ms 23112 KB Output is correct
36 Correct 109 ms 23000 KB Output is correct
37 Correct 97 ms 23000 KB Output is correct
38 Correct 104 ms 23100 KB Output is correct
39 Correct 91 ms 23112 KB Output is correct
40 Correct 138 ms 23016 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 2 ms 4596 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4600 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 358 ms 19192 KB Output is correct
12 Correct 347 ms 19016 KB Output is correct
13 Correct 390 ms 18076 KB Output is correct
14 Correct 402 ms 18248 KB Output is correct
15 Correct 385 ms 19272 KB Output is correct
16 Correct 465 ms 18328 KB Output is correct
17 Correct 428 ms 18248 KB Output is correct
18 Correct 233 ms 20208 KB Output is correct
19 Correct 356 ms 17224 KB Output is correct
20 Correct 350 ms 19016 KB Output is correct
21 Correct 434 ms 22344 KB Output is correct
22 Correct 436 ms 22344 KB Output is correct
23 Correct 493 ms 21492 KB Output is correct
24 Correct 574 ms 21320 KB Output is correct
25 Correct 460 ms 23244 KB Output is correct
26 Correct 548 ms 21620 KB Output is correct
27 Correct 569 ms 21576 KB Output is correct
28 Correct 266 ms 24136 KB Output is correct
29 Correct 412 ms 20200 KB Output is correct
30 Correct 431 ms 22344 KB Output is correct
31 Correct 523 ms 22064 KB Output is correct
32 Correct 595 ms 22108 KB Output is correct
33 Correct 466 ms 21072 KB Output is correct
34 Correct 573 ms 20812 KB Output is correct
35 Correct 571 ms 21704 KB Output is correct
36 Correct 281 ms 20560 KB Output is correct
37 Correct 412 ms 22280 KB Output is correct
38 Correct 441 ms 20324 KB Output is correct
39 Correct 516 ms 21400 KB Output is correct
40 Correct 578 ms 21140 KB Output is correct
41 Correct 103 ms 23256 KB Output is correct
42 Correct 77 ms 23112 KB Output is correct
43 Correct 91 ms 23128 KB Output is correct
44 Correct 108 ms 22856 KB Output is correct
45 Correct 76 ms 23120 KB Output is correct
46 Correct 134 ms 23112 KB Output is correct
47 Correct 99 ms 23116 KB Output is correct
48 Correct 60 ms 23252 KB Output is correct
49 Correct 73 ms 22856 KB Output is correct
50 Correct 75 ms 23120 KB Output is correct
51 Correct 91 ms 23052 KB Output is correct
52 Correct 98 ms 23112 KB Output is correct
53 Correct 77 ms 22992 KB Output is correct
54 Correct 104 ms 23112 KB Output is correct
55 Correct 102 ms 22888 KB Output is correct
56 Correct 60 ms 23112 KB Output is correct
57 Correct 95 ms 23052 KB Output is correct
58 Correct 75 ms 23004 KB Output is correct
59 Correct 84 ms 23112 KB Output is correct
60 Correct 105 ms 23112 KB Output is correct
61 Correct 77 ms 23128 KB Output is correct
62 Correct 107 ms 23000 KB Output is correct
63 Correct 107 ms 23000 KB Output is correct
64 Correct 59 ms 23112 KB Output is correct
65 Correct 99 ms 23112 KB Output is correct
66 Correct 109 ms 23000 KB Output is correct
67 Correct 97 ms 23000 KB Output is correct
68 Correct 104 ms 23100 KB Output is correct
69 Correct 91 ms 23112 KB Output is correct
70 Correct 138 ms 23016 KB Output is correct
71 Correct 785 ms 47304 KB Output is correct
72 Correct 781 ms 47048 KB Output is correct
73 Correct 950 ms 45264 KB Output is correct
74 Correct 1281 ms 46408 KB Output is correct
75 Correct 716 ms 48456 KB Output is correct
76 Correct 1248 ms 46812 KB Output is correct
77 Correct 1140 ms 46556 KB Output is correct
78 Correct 401 ms 50360 KB Output is correct
79 Correct 679 ms 44416 KB Output is correct
80 Correct 744 ms 47612 KB Output is correct
81 Correct 967 ms 47432 KB Output is correct
82 Correct 1140 ms 46412 KB Output is correct
83 Correct 678 ms 45824 KB Output is correct
84 Correct 1329 ms 46484 KB Output is correct
85 Correct 1229 ms 46556 KB Output is correct
86 Correct 406 ms 44360 KB Output is correct
87 Correct 718 ms 47432 KB Output is correct
88 Correct 713 ms 44504 KB Output is correct
89 Correct 855 ms 46008 KB Output is correct
90 Correct 1120 ms 46408 KB Output is correct
91 Correct 657 ms 45640 KB Output is correct
92 Correct 1251 ms 46816 KB Output is correct
93 Correct 1194 ms 46576 KB Output is correct
94 Correct 387 ms 44504 KB Output is correct
95 Correct 1004 ms 46664 KB Output is correct
96 Correct 995 ms 46560 KB Output is correct
97 Correct 964 ms 46664 KB Output is correct
98 Correct 1084 ms 46428 KB Output is correct
99 Correct 1080 ms 46452 KB Output is correct
100 Correct 988 ms 46664 KB Output is correct