oj.uz

Submission #568566

# Submission time Handle Problem Language Result Execution time Memory
568566 2022-05-25T17:10:09 Z FEDIKUS Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1368 ms 47440 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
#define fb(i,s,f) for(ll (i)=s-1;(i)>=f;(i)--)
#define ffi(i,s,f) for(ll (i)=s;(i)<=(f);(i)++)
#define fbi(i,s,f) for(ll (i)=s;(i)>=(f);(i)--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,ll) sort(a.begin(),a.end(),greater<ll>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<ll,ll> pll;
typedef string str;

const ll logg=20;

ll sub[1LL<<logg],sup[1LL<<logg];

ll com(ll a){
    return a^((1LL<<logg)-1);
}

void solve(){
    ll l,q;
    cin>>l>>q;
    str s;
    cin>>s;
    ff(mask,0,(1LL<<l)) sub[mask]=s[mask]-'0';
    ff(i,0,logg) ff(mask,0,(1LL<<logg)) if((1LL<<i)&mask) sub[mask]+=sub[mask^(1LL<<i)];
    ff(mask,0,(1LL<<l)) sup[mask]=s[mask]-'0';
    ff(i,0,logg) ff(mask,0,(1LL<<logg)) if((1LL<<i)&com(mask)) sup[mask]+=sup[mask^(1LL<<i)];
    while(q--){
        str t;
        cin>>t;
        ll one=0,zero=0;
        for(char i:t) if(i=='0') zero++; else if(i=='1') one++;
        ll res=0;
        if(one<=6){
            ll mask=0;
            ll nfixed=0;
            ff(i,0,l){
                if(t[i]=='1') mask+=(1LL<<(l-i-1));
                if(t[i]=='?') nfixed+=(1LL<<(l-i-1));
            }
            for(ll submask=mask;;submask=(submask-1)&mask){
                if((one-__builtin_popcount(submask|nfixed))&1) res-=sub[submask|nfixed];
                else res+=sub[submask|nfixed];
                if(submask==0) break;
            }
        }else if(zero<=6){
            ll mask=0;
            ll ones=0;
            ff(i,0,l){
                if(t[i]=='0') mask+=(1LL<<(l-i-1));
                if(t[i]=='1') ones+=(1LL<<(l-i-1));
            }
            for(ll submask=mask;;submask=(submask-1)&mask){
                if(__builtin_popcount(submask)&1) res-=sup[submask|ones];
                else res+=sup[submask|ones];
                if(submask==0) break;
            }
        }else{
            ll mask=0;
            ll fixed=0;
            ff(i,0,l){
                if(t[i]=='?') mask+=(1LL<<(l-i-1));
                else if(t[i]=='1') fixed+=(1LL<<(l-i-1));
            }
            for(ll submask=mask;;submask=(submask-1)&mask){
                res+=s[submask|fixed]-'0';
                if(submask==0) break;
            }
        }
        cout<<abs(res)<<"\n";
    }
}

int main(){
    ios;
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Compilation message

snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'mask' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:40:5: note: in expansion of macro 'ff'
   40 |     ff(mask,0,(1LL<<l)) sub[mask]=s[mask]-'0';
      |     ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:41:5: note: in expansion of macro 'ff'
   41 |     ff(i,0,logg) ff(mask,0,(1LL<<logg)) if((1LL<<i)&mask) sub[mask]+=sub[mask^(1LL<<i)];
      |     ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'mask' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:41:18: note: in expansion of macro 'ff'
   41 |     ff(i,0,logg) ff(mask,0,(1LL<<logg)) if((1LL<<i)&mask) sub[mask]+=sub[mask^(1LL<<i)];
      |                  ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'mask' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:42:5: note: in expansion of macro 'ff'
   42 |     ff(mask,0,(1LL<<l)) sup[mask]=s[mask]-'0';
      |     ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:43:5: note: in expansion of macro 'ff'
   43 |     ff(i,0,logg) ff(mask,0,(1LL<<logg)) if((1LL<<i)&com(mask)) sup[mask]+=sup[mask^(1LL<<i)];
      |     ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'mask' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:43:18: note: in expansion of macro 'ff'
   43 |     ff(i,0,logg) ff(mask,0,(1LL<<logg)) if((1LL<<i)&com(mask)) sup[mask]+=sup[mask^(1LL<<i)];
      |                  ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:53:13: note: in expansion of macro 'ff'
   53 |             ff(i,0,l){
      |             ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:65:13: note: in expansion of macro 'ff'
   65 |             ff(i,0,l){
      |             ^~
snake_escaping.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                          ^
snake_escaping.cpp:77:13: note: in expansion of macro 'ff'
   77 |             ff(i,0,l){
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16720 KB Output is correct
2 Correct 57 ms 16724 KB Output is correct
3 Correct 52 ms 16712 KB Output is correct
4 Correct 54 ms 16712 KB Output is correct
5 Correct 66 ms 16724 KB Output is correct
6 Correct 48 ms 16728 KB Output is correct
7 Correct 61 ms 16716 KB Output is correct
8 Correct 53 ms 16716 KB Output is correct
9 Correct 49 ms 16724 KB Output is correct
10 Correct 51 ms 16712 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16720 KB Output is correct
2 Correct 57 ms 16724 KB Output is correct
3 Correct 52 ms 16712 KB Output is correct
4 Correct 54 ms 16712 KB Output is correct
5 Correct 66 ms 16724 KB Output is correct
6 Correct 48 ms 16728 KB Output is correct
7 Correct 61 ms 16716 KB Output is correct
8 Correct 53 ms 16716 KB Output is correct
9 Correct 49 ms 16724 KB Output is correct
10 Correct 51 ms 16712 KB Output is correct
11 Correct 438 ms 20696 KB Output is correct
12 Correct 272 ms 20320 KB Output is correct
13 Correct 320 ms 19536 KB Output is correct
14 Correct 360 ms 19664 KB Output is correct
15 Correct 284 ms 20684 KB Output is correct
16 Correct 414 ms 19960 KB Output is correct
17 Correct 354 ms 19924 KB Output is correct
18 Correct 219 ms 21704 KB Output is correct
19 Correct 420 ms 18744 KB Output is correct
20 Correct 438 ms 20376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16720 KB Output is correct
2 Correct 57 ms 16724 KB Output is correct
3 Correct 52 ms 16712 KB Output is correct
4 Correct 54 ms 16712 KB Output is correct
5 Correct 66 ms 16724 KB Output is correct
6 Correct 48 ms 16728 KB Output is correct
7 Correct 61 ms 16716 KB Output is correct
8 Correct 53 ms 16716 KB Output is correct
9 Correct 49 ms 16724 KB Output is correct
10 Correct 51 ms 16712 KB Output is correct
11 Correct 438 ms 20696 KB Output is correct
12 Correct 272 ms 20320 KB Output is correct
13 Correct 320 ms 19536 KB Output is correct
14 Correct 360 ms 19664 KB Output is correct
15 Correct 284 ms 20684 KB Output is correct
16 Correct 414 ms 19960 KB Output is correct
17 Correct 354 ms 19924 KB Output is correct
18 Correct 219 ms 21704 KB Output is correct
19 Correct 420 ms 18744 KB Output is correct
20 Correct 438 ms 20376 KB Output is correct
21 Correct 542 ms 20740 KB Output is correct
22 Correct 315 ms 20896 KB Output is correct
23 Correct 406 ms 19892 KB Output is correct
24 Correct 433 ms 19736 KB Output is correct
25 Correct 325 ms 21684 KB Output is correct
26 Correct 432 ms 20300 KB Output is correct
27 Correct 398 ms 20196 KB Output is correct
28 Correct 244 ms 22860 KB Output is correct
29 Correct 518 ms 18988 KB Output is correct
30 Correct 356 ms 20924 KB Output is correct
31 Correct 391 ms 20884 KB Output is correct
32 Correct 382 ms 20820 KB Output is correct
33 Correct 318 ms 19728 KB Output is correct
34 Correct 458 ms 19852 KB Output is correct
35 Correct 419 ms 20284 KB Output is correct
36 Correct 222 ms 18836 KB Output is correct
37 Correct 327 ms 20772 KB Output is correct
38 Correct 478 ms 18860 KB Output is correct
39 Correct 596 ms 19992 KB Output is correct
40 Correct 452 ms 19972 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16720 KB Output is correct
2 Correct 57 ms 16724 KB Output is correct
3 Correct 52 ms 16712 KB Output is correct
4 Correct 54 ms 16712 KB Output is correct
5 Correct 66 ms 16724 KB Output is correct
6 Correct 48 ms 16728 KB Output is correct
7 Correct 61 ms 16716 KB Output is correct
8 Correct 53 ms 16716 KB Output is correct
9 Correct 49 ms 16724 KB Output is correct
10 Correct 51 ms 16712 KB Output is correct
11 Correct 65 ms 18004 KB Output is correct
12 Correct 76 ms 18084 KB Output is correct
13 Correct 99 ms 18016 KB Output is correct
14 Correct 122 ms 18116 KB Output is correct
15 Correct 77 ms 18136 KB Output is correct
16 Correct 116 ms 18120 KB Output is correct
17 Correct 103 ms 18016 KB Output is correct
18 Correct 68 ms 19028 KB Output is correct
19 Correct 69 ms 20024 KB Output is correct
20 Correct 81 ms 20172 KB Output is correct
21 Correct 79 ms 20176 KB Output is correct
22 Correct 127 ms 20040 KB Output is correct
23 Correct 78 ms 20056 KB Output is correct
24 Correct 106 ms 20196 KB Output is correct
25 Correct 93 ms 20076 KB Output is correct
26 Correct 64 ms 19912 KB Output is correct
27 Correct 80 ms 20160 KB Output is correct
28 Correct 71 ms 19996 KB Output is correct
29 Correct 85 ms 20076 KB Output is correct
30 Correct 78 ms 20044 KB Output is correct
31 Correct 78 ms 20048 KB Output is correct
32 Correct 106 ms 20044 KB Output is correct
33 Correct 94 ms 20040 KB Output is correct
34 Correct 68 ms 19920 KB Output is correct
35 Correct 96 ms 20132 KB Output is correct
36 Correct 95 ms 20056 KB Output is correct
37 Correct 100 ms 20032 KB Output is correct
38 Correct 114 ms 20028 KB Output is correct
39 Correct 93 ms 20012 KB Output is correct
40 Correct 83 ms 20056 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16720 KB Output is correct
2 Correct 57 ms 16724 KB Output is correct
3 Correct 52 ms 16712 KB Output is correct
4 Correct 54 ms 16712 KB Output is correct
5 Correct 66 ms 16724 KB Output is correct
6 Correct 48 ms 16728 KB Output is correct
7 Correct 61 ms 16716 KB Output is correct
8 Correct 53 ms 16716 KB Output is correct
9 Correct 49 ms 16724 KB Output is correct
10 Correct 51 ms 16712 KB Output is correct
11 Correct 438 ms 20696 KB Output is correct
12 Correct 272 ms 20320 KB Output is correct
13 Correct 320 ms 19536 KB Output is correct
14 Correct 360 ms 19664 KB Output is correct
15 Correct 284 ms 20684 KB Output is correct
16 Correct 414 ms 19960 KB Output is correct
17 Correct 354 ms 19924 KB Output is correct
18 Correct 219 ms 21704 KB Output is correct
19 Correct 420 ms 18744 KB Output is correct
20 Correct 438 ms 20376 KB Output is correct
21 Correct 542 ms 20740 KB Output is correct
22 Correct 315 ms 20896 KB Output is correct
23 Correct 406 ms 19892 KB Output is correct
24 Correct 433 ms 19736 KB Output is correct
25 Correct 325 ms 21684 KB Output is correct
26 Correct 432 ms 20300 KB Output is correct
27 Correct 398 ms 20196 KB Output is correct
28 Correct 244 ms 22860 KB Output is correct
29 Correct 518 ms 18988 KB Output is correct
30 Correct 356 ms 20924 KB Output is correct
31 Correct 391 ms 20884 KB Output is correct
32 Correct 382 ms 20820 KB Output is correct
33 Correct 318 ms 19728 KB Output is correct
34 Correct 458 ms 19852 KB Output is correct
35 Correct 419 ms 20284 KB Output is correct
36 Correct 222 ms 18836 KB Output is correct
37 Correct 327 ms 20772 KB Output is correct
38 Correct 478 ms 18860 KB Output is correct
39 Correct 596 ms 19992 KB Output is correct
40 Correct 452 ms 19972 KB Output is correct
41 Correct 65 ms 18004 KB Output is correct
42 Correct 76 ms 18084 KB Output is correct
43 Correct 99 ms 18016 KB Output is correct
44 Correct 122 ms 18116 KB Output is correct
45 Correct 77 ms 18136 KB Output is correct
46 Correct 116 ms 18120 KB Output is correct
47 Correct 103 ms 18016 KB Output is correct
48 Correct 68 ms 19028 KB Output is correct
49 Correct 69 ms 20024 KB Output is correct
50 Correct 81 ms 20172 KB Output is correct
51 Correct 79 ms 20176 KB Output is correct
52 Correct 127 ms 20040 KB Output is correct
53 Correct 78 ms 20056 KB Output is correct
54 Correct 106 ms 20196 KB Output is correct
55 Correct 93 ms 20076 KB Output is correct
56 Correct 64 ms 19912 KB Output is correct
57 Correct 80 ms 20160 KB Output is correct
58 Correct 71 ms 19996 KB Output is correct
59 Correct 85 ms 20076 KB Output is correct
60 Correct 78 ms 20044 KB Output is correct
61 Correct 78 ms 20048 KB Output is correct
62 Correct 106 ms 20044 KB Output is correct
63 Correct 94 ms 20040 KB Output is correct
64 Correct 68 ms 19920 KB Output is correct
65 Correct 96 ms 20132 KB Output is correct
66 Correct 95 ms 20056 KB Output is correct
67 Correct 100 ms 20032 KB Output is correct
68 Correct 114 ms 20028 KB Output is correct
69 Correct 93 ms 20012 KB Output is correct
70 Correct 83 ms 20056 KB Output is correct
71 Correct 360 ms 44416 KB Output is correct
72 Correct 486 ms 44524 KB Output is correct
73 Correct 768 ms 43040 KB Output is correct
74 Correct 1215 ms 43448 KB Output is correct
75 Correct 482 ms 45576 KB Output is correct
76 Correct 1368 ms 43828 KB Output is correct
77 Correct 1029 ms 43600 KB Output is correct
78 Correct 307 ms 47440 KB Output is correct
79 Correct 378 ms 41400 KB Output is correct
80 Correct 411 ms 44524 KB Output is correct
81 Correct 748 ms 44524 KB Output is correct
82 Correct 1225 ms 43392 KB Output is correct
83 Correct 508 ms 42548 KB Output is correct
84 Correct 1133 ms 43448 KB Output is correct
85 Correct 1030 ms 43804 KB Output is correct
86 Correct 322 ms 41348 KB Output is correct
87 Correct 481 ms 44468 KB Output is correct
88 Correct 480 ms 41456 KB Output is correct
89 Correct 725 ms 43316 KB Output is correct
90 Correct 544 ms 43456 KB Output is correct
91 Correct 513 ms 42740 KB Output is correct
92 Correct 1250 ms 43912 KB Output is correct
93 Correct 1038 ms 43568 KB Output is correct
94 Correct 307 ms 41404 KB Output is correct
95 Correct 863 ms 43432 KB Output is correct
96 Correct 849 ms 43468 KB Output is correct
97 Correct 847 ms 43560 KB Output is correct
98 Correct 794 ms 43648 KB Output is correct
99 Correct 802 ms 43552 KB Output is correct
100 Correct 805 ms 43472 KB Output is correct