oj.uz

Submission #934121

# Submission time Handle Problem Language Result Execution time Memory
934121 2024-02-26T20:03:42 Z Rafi22 Snake Escaping (JOI18_snake_escaping) C++14
100 / 100
 687 ms 41880 KB 
#include <bits/stdc++.h>

//#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int infl=1000000000000000007;
int inf=1000000007;
int mod=1000000007;
int mod1=998244353;

const bool multi=1;

const int N=(1<<20)+7;

int cnt[N];
int ile1[N];
int ile0[N];

int ans,z;
vector<int>Z,V0,V1;

void bt(int m,int i)
{
    if(i==sz(Z))
    {
        ans+=cnt[m];
        return ;
    }
    bt(m,i+1);
    bt(m^(1<<Z[i]),i+1);
}

void bt1(int m,int i,int p)
{
    if(i==sz(V1))
    {
        if(p) ans-=ile1[m^z];
        else ans+=ile1[m^z];
        return ;
    }
    bt1(m,i+1,p^1);
    bt1(m^(1<<V1[i]),i+1,p);
}

void bt2(int m,int i,int p)
{
    if(i==sz(V0))
    {
        if(p) ans-=ile0[m^z];
        else ans+=ile0[m^z];
        return ;
    }
    bt2(m,i+1,p^1);
    bt2(m^(1<<V0[i]),i+1,p);
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=0;i<(1<<n);i++)
    {
        char c;
        cin>>c;
        cnt[i]=c-'0';
        ile1[i]=cnt[i];
        ile0[(1<<n)-1-i]=cnt[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int m=0;m<(1<<n);m++)
        {
            if(m&(1<<i))
            {
                ile1[m]+=ile1[m^(1<<i)];
                ile0[m]+=ile0[m^(1<<i)];
            }
        }
    }
    while(q--)
    {
        string s;
        cin>>s;
        reverse(all(s));
        Z.clear(),V0.clear(),V1.clear();
        ans=0,z=0;
        int msk=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='?')
            {
                Z.pb(i);
                z^=(1<<i);
            }
            else if(s[i]=='0') V0.pb(i);
            else
            {
                V1.pb(i);
                msk^=(1<<i);
            }
        }
        if(sz(Z)<=6) bt(msk,0);
        else if(sz(V1)<=6) bt1(0,0,0);
        else bt2(0,0,0);
        cout<<ans<<endl;
    }


    return 0;
}

Compilation message

snake_escaping.cpp:13:10: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000000007' to '-1486618617' [-Woverflow]
   13 | int infl=1000000000000000007;
      |          ^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 277 ms 8644 KB Output is correct
12 Correct 277 ms 8020 KB Output is correct
13 Correct 227 ms 7252 KB Output is correct
14 Correct 227 ms 7564 KB Output is correct
15 Correct 387 ms 8528 KB Output is correct
16 Correct 260 ms 7504 KB Output is correct
17 Correct 264 ms 7504 KB Output is correct
18 Correct 150 ms 9424 KB Output is correct
19 Correct 171 ms 6484 KB Output is correct
20 Correct 265 ms 8016 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 277 ms 8644 KB Output is correct
12 Correct 277 ms 8020 KB Output is correct
13 Correct 227 ms 7252 KB Output is correct
14 Correct 227 ms 7564 KB Output is correct
15 Correct 387 ms 8528 KB Output is correct
16 Correct 260 ms 7504 KB Output is correct
17 Correct 264 ms 7504 KB Output is correct
18 Correct 150 ms 9424 KB Output is correct
19 Correct 171 ms 6484 KB Output is correct
20 Correct 265 ms 8016 KB Output is correct
21 Correct 448 ms 8804 KB Output is correct
22 Correct 281 ms 8736 KB Output is correct
23 Correct 289 ms 7840 KB Output is correct
24 Correct 277 ms 7516 KB Output is correct
25 Correct 267 ms 9368 KB Output is correct
26 Correct 315 ms 7916 KB Output is correct
27 Correct 312 ms 8016 KB Output is correct
28 Correct 166 ms 10580 KB Output is correct
29 Correct 196 ms 6484 KB Output is correct
30 Correct 363 ms 8528 KB Output is correct
31 Correct 426 ms 8528 KB Output is correct
32 Correct 335 ms 8908 KB Output is correct
33 Correct 258 ms 7488 KB Output is correct
34 Correct 287 ms 7748 KB Output is correct
35 Correct 312 ms 7860 KB Output is correct
36 Correct 154 ms 6480 KB Output is correct
37 Correct 386 ms 8528 KB Output is correct
38 Correct 212 ms 6508 KB Output is correct
39 Correct 280 ms 7776 KB Output is correct
40 Correct 292 ms 7488 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 41 ms 12884 KB Output is correct
12 Correct 44 ms 14928 KB Output is correct
13 Correct 51 ms 14928 KB Output is correct
14 Correct 60 ms 14928 KB Output is correct
15 Correct 49 ms 14928 KB Output is correct
16 Correct 59 ms 14864 KB Output is correct
17 Correct 57 ms 14932 KB Output is correct
18 Correct 39 ms 15188 KB Output is correct
19 Correct 43 ms 14676 KB Output is correct
20 Correct 44 ms 15044 KB Output is correct
21 Correct 51 ms 14932 KB Output is correct
22 Correct 63 ms 15060 KB Output is correct
23 Correct 46 ms 14932 KB Output is correct
24 Correct 58 ms 14928 KB Output is correct
25 Correct 55 ms 14928 KB Output is correct
26 Correct 37 ms 14676 KB Output is correct
27 Correct 51 ms 15056 KB Output is correct
28 Correct 42 ms 14688 KB Output is correct
29 Correct 49 ms 14892 KB Output is correct
30 Correct 59 ms 14932 KB Output is correct
31 Correct 46 ms 14792 KB Output is correct
32 Correct 60 ms 14792 KB Output is correct
33 Correct 76 ms 14852 KB Output is correct
34 Correct 40 ms 14716 KB Output is correct
35 Correct 52 ms 14936 KB Output is correct
36 Correct 52 ms 14804 KB Output is correct
37 Correct 52 ms 14908 KB Output is correct
38 Correct 54 ms 14932 KB Output is correct
39 Correct 52 ms 14928 KB Output is correct
40 Correct 52 ms 14932 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 277 ms 8644 KB Output is correct
12 Correct 277 ms 8020 KB Output is correct
13 Correct 227 ms 7252 KB Output is correct
14 Correct 227 ms 7564 KB Output is correct
15 Correct 387 ms 8528 KB Output is correct
16 Correct 260 ms 7504 KB Output is correct
17 Correct 264 ms 7504 KB Output is correct
18 Correct 150 ms 9424 KB Output is correct
19 Correct 171 ms 6484 KB Output is correct
20 Correct 265 ms 8016 KB Output is correct
21 Correct 448 ms 8804 KB Output is correct
22 Correct 281 ms 8736 KB Output is correct
23 Correct 289 ms 7840 KB Output is correct
24 Correct 277 ms 7516 KB Output is correct
25 Correct 267 ms 9368 KB Output is correct
26 Correct 315 ms 7916 KB Output is correct
27 Correct 312 ms 8016 KB Output is correct
28 Correct 166 ms 10580 KB Output is correct
29 Correct 196 ms 6484 KB Output is correct
30 Correct 363 ms 8528 KB Output is correct
31 Correct 426 ms 8528 KB Output is correct
32 Correct 335 ms 8908 KB Output is correct
33 Correct 258 ms 7488 KB Output is correct
34 Correct 287 ms 7748 KB Output is correct
35 Correct 312 ms 7860 KB Output is correct
36 Correct 154 ms 6480 KB Output is correct
37 Correct 386 ms 8528 KB Output is correct
38 Correct 212 ms 6508 KB Output is correct
39 Correct 280 ms 7776 KB Output is correct
40 Correct 292 ms 7488 KB Output is correct
41 Correct 41 ms 12884 KB Output is correct
42 Correct 44 ms 14928 KB Output is correct
43 Correct 51 ms 14928 KB Output is correct
44 Correct 60 ms 14928 KB Output is correct
45 Correct 49 ms 14928 KB Output is correct
46 Correct 59 ms 14864 KB Output is correct
47 Correct 57 ms 14932 KB Output is correct
48 Correct 39 ms 15188 KB Output is correct
49 Correct 43 ms 14676 KB Output is correct
50 Correct 44 ms 15044 KB Output is correct
51 Correct 51 ms 14932 KB Output is correct
52 Correct 63 ms 15060 KB Output is correct
53 Correct 46 ms 14932 KB Output is correct
54 Correct 58 ms 14928 KB Output is correct
55 Correct 55 ms 14928 KB Output is correct
56 Correct 37 ms 14676 KB Output is correct
57 Correct 51 ms 15056 KB Output is correct
58 Correct 42 ms 14688 KB Output is correct
59 Correct 49 ms 14892 KB Output is correct
60 Correct 59 ms 14932 KB Output is correct
61 Correct 46 ms 14792 KB Output is correct
62 Correct 60 ms 14792 KB Output is correct
63 Correct 76 ms 14852 KB Output is correct
64 Correct 40 ms 14716 KB Output is correct
65 Correct 52 ms 14936 KB Output is correct
66 Correct 52 ms 14804 KB Output is correct
67 Correct 52 ms 14908 KB Output is correct
68 Correct 54 ms 14932 KB Output is correct
69 Correct 52 ms 14928 KB Output is correct
70 Correct 52 ms 14932 KB Output is correct
71 Correct 339 ms 39248 KB Output is correct
72 Correct 359 ms 39436 KB Output is correct
73 Correct 468 ms 38128 KB Output is correct
74 Correct 687 ms 38228 KB Output is correct
75 Correct 430 ms 40272 KB Output is correct
76 Correct 678 ms 38520 KB Output is correct
77 Correct 623 ms 38480 KB Output is correct
78 Correct 259 ms 41880 KB Output is correct
79 Correct 351 ms 36448 KB Output is correct
80 Correct 380 ms 39404 KB Output is correct
81 Correct 516 ms 39252 KB Output is correct
82 Correct 674 ms 38124 KB Output is correct
83 Correct 385 ms 37316 KB Output is correct
84 Correct 632 ms 38432 KB Output is correct
85 Correct 610 ms 38460 KB Output is correct
86 Correct 236 ms 36040 KB Output is correct
87 Correct 367 ms 39216 KB Output is correct
88 Correct 365 ms 36064 KB Output is correct
89 Correct 469 ms 37884 KB Output is correct
90 Correct 616 ms 38228 KB Output is correct
91 Correct 386 ms 37460 KB Output is correct
92 Correct 642 ms 38512 KB Output is correct
93 Correct 606 ms 38400 KB Output is correct
94 Correct 236 ms 36068 KB Output is correct
95 Correct 530 ms 38288 KB Output is correct
96 Correct 535 ms 38140 KB Output is correct
97 Correct 525 ms 38228 KB Output is correct
98 Correct 526 ms 38388 KB Output is correct
99 Correct 541 ms 38248 KB Output is correct
100 Correct 534 ms 38332 KB Output is correct