oj.uz

Submission #568560

# Submission time Handle Problem Language Result Execution time Memory
568560 2022-05-25T16:58:55 Z FEDIKUS Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 632 ms 50124 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=21;

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

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

void solve(){
    ll l,q;
    cin>>l>>q;
    str s;
    cin>>s;
    ff(mask,0,(1<<l)) sub[mask]=s[mask]-'0';
    ff(i,0,logg) ff(mask,0,(1<<logg)) if((1<<i)&mask) sub[mask]+=sub[mask^(1<<i)];
    ff(mask,0,(1<<l)) sup[mask]=s[mask]-'0';
    ff(i,0,logg) ff(mask,0,(1<<logg)) if((1<<i)&com(mask)) sup[mask]+=sup[mask^(1<<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,t.size()){
                if(t[i]=='1') mask+=(1<<(l-i-1));
                if(t[i]=='?') nfixed+=(1<<(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,t.size()){
                if(t[i]=='0') mask+=(1<<(l-i-1));
                if(t[i]=='1') ones+=(1<<(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;
            ff(i,0,t.size()){
                if(t[i]=='?') mask+=(1<<(l-i-1));
            }
            for(ll submask=mask;;submask=(submask-1)&mask){
                res+=s[submask]-'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,(1<<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,(1<<logg)) if((1<<i)&mask) sub[mask]+=sub[mask^(1<<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,(1<<logg)) if((1<<i)&mask) sub[mask]+=sub[mask^(1<<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,(1<<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,(1<<logg)) if((1<<i)&com(mask)) sup[mask]+=sup[mask^(1<<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,(1<<logg)) if((1<<i)&com(mask)) sup[mask]+=sup[mask^(1<<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,t.size()){
      |             ^~
snake_escaping.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    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,t.size()){
      |             ^~
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,t.size()){
      |             ^~
snake_escaping.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    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,t.size()){
      |             ^~
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:76:13: note: in expansion of macro 'ff'
   76 |             ff(i,0,t.size()){
      |             ^~
snake_escaping.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define ff(i,s,f) for(ll (i)=s;(i)<(f);(i)++)
      |                                ~~~^~~~
snake_escaping.cpp:76:13: note: in expansion of macro 'ff'
   76 |             ff(i,0,t.size()){
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33136 KB Output is correct
2 Correct 112 ms 33052 KB Output is correct
3 Correct 112 ms 33120 KB Output is correct
4 Correct 113 ms 33100 KB Output is correct
5 Correct 120 ms 33120 KB Output is correct
6 Correct 112 ms 33144 KB Output is correct
7 Correct 117 ms 33100 KB Output is correct
8 Correct 115 ms 33140 KB Output is correct
9 Correct 117 ms 33252 KB Output is correct
10 Correct 117 ms 33100 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33136 KB Output is correct
2 Correct 112 ms 33052 KB Output is correct
3 Correct 112 ms 33120 KB Output is correct
4 Correct 113 ms 33100 KB Output is correct
5 Correct 120 ms 33120 KB Output is correct
6 Correct 112 ms 33144 KB Output is correct
7 Correct 117 ms 33100 KB Output is correct
8 Correct 115 ms 33140 KB Output is correct
9 Correct 117 ms 33252 KB Output is correct
10 Correct 117 ms 33100 KB Output is correct
11 Correct 460 ms 47872 KB Output is correct
12 Correct 350 ms 47524 KB Output is correct
13 Correct 382 ms 47008 KB Output is correct
14 Correct 386 ms 46948 KB Output is correct
15 Correct 360 ms 47880 KB Output is correct
16 Correct 424 ms 47056 KB Output is correct
17 Correct 471 ms 47052 KB Output is correct
18 Correct 287 ms 48980 KB Output is correct
19 Correct 444 ms 45796 KB Output is correct
20 Correct 417 ms 47756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33136 KB Output is correct
2 Correct 112 ms 33052 KB Output is correct
3 Correct 112 ms 33120 KB Output is correct
4 Correct 113 ms 33100 KB Output is correct
5 Correct 120 ms 33120 KB Output is correct
6 Correct 112 ms 33144 KB Output is correct
7 Correct 117 ms 33100 KB Output is correct
8 Correct 115 ms 33140 KB Output is correct
9 Correct 117 ms 33252 KB Output is correct
10 Correct 117 ms 33100 KB Output is correct
11 Correct 460 ms 47872 KB Output is correct
12 Correct 350 ms 47524 KB Output is correct
13 Correct 382 ms 47008 KB Output is correct
14 Correct 386 ms 46948 KB Output is correct
15 Correct 360 ms 47880 KB Output is correct
16 Correct 424 ms 47056 KB Output is correct
17 Correct 471 ms 47052 KB Output is correct
18 Correct 287 ms 48980 KB Output is correct
19 Correct 444 ms 45796 KB Output is correct
20 Correct 417 ms 47756 KB Output is correct
21 Correct 573 ms 49964 KB Output is correct
22 Correct 396 ms 50124 KB Output is correct
23 Correct 486 ms 49196 KB Output is correct
24 Correct 476 ms 48732 KB Output is correct
25 Correct 408 ms 49980 KB Output is correct
26 Correct 506 ms 48052 KB Output is correct
27 Correct 500 ms 47048 KB Output is correct
28 Correct 297 ms 48536 KB Output is correct
29 Correct 564 ms 44320 KB Output is correct
30 Correct 427 ms 45572 KB Output is correct
31 Correct 457 ms 44672 KB Output is correct
32 Correct 469 ms 44140 KB Output is correct
33 Correct 390 ms 42112 KB Output is correct
34 Correct 507 ms 41732 KB Output is correct
35 Correct 512 ms 41600 KB Output is correct
36 Correct 296 ms 39424 KB Output is correct
37 Correct 401 ms 41048 KB Output is correct
38 Correct 535 ms 38608 KB Output is correct
39 Correct 632 ms 39500 KB Output is correct
40 Correct 512 ms 38468 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33136 KB Output is correct
2 Correct 112 ms 33052 KB Output is correct
3 Correct 112 ms 33120 KB Output is correct
4 Correct 113 ms 33100 KB Output is correct
5 Correct 120 ms 33120 KB Output is correct
6 Correct 112 ms 33144 KB Output is correct
7 Correct 117 ms 33100 KB Output is correct
8 Correct 115 ms 33140 KB Output is correct
9 Correct 117 ms 33252 KB Output is correct
10 Correct 117 ms 33100 KB Output is correct
11 Correct 144 ms 36212 KB Output is correct
12 Correct 153 ms 36020 KB Output is correct
13 Incorrect 170 ms 35900 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33136 KB Output is correct
2 Correct 112 ms 33052 KB Output is correct
3 Correct 112 ms 33120 KB Output is correct
4 Correct 113 ms 33100 KB Output is correct
5 Correct 120 ms 33120 KB Output is correct
6 Correct 112 ms 33144 KB Output is correct
7 Correct 117 ms 33100 KB Output is correct
8 Correct 115 ms 33140 KB Output is correct
9 Correct 117 ms 33252 KB Output is correct
10 Correct 117 ms 33100 KB Output is correct
11 Correct 460 ms 47872 KB Output is correct
12 Correct 350 ms 47524 KB Output is correct
13 Correct 382 ms 47008 KB Output is correct
14 Correct 386 ms 46948 KB Output is correct
15 Correct 360 ms 47880 KB Output is correct
16 Correct 424 ms 47056 KB Output is correct
17 Correct 471 ms 47052 KB Output is correct
18 Correct 287 ms 48980 KB Output is correct
19 Correct 444 ms 45796 KB Output is correct
20 Correct 417 ms 47756 KB Output is correct
21 Correct 573 ms 49964 KB Output is correct
22 Correct 396 ms 50124 KB Output is correct
23 Correct 486 ms 49196 KB Output is correct
24 Correct 476 ms 48732 KB Output is correct
25 Correct 408 ms 49980 KB Output is correct
26 Correct 506 ms 48052 KB Output is correct
27 Correct 500 ms 47048 KB Output is correct
28 Correct 297 ms 48536 KB Output is correct
29 Correct 564 ms 44320 KB Output is correct
30 Correct 427 ms 45572 KB Output is correct
31 Correct 457 ms 44672 KB Output is correct
32 Correct 469 ms 44140 KB Output is correct
33 Correct 390 ms 42112 KB Output is correct
34 Correct 507 ms 41732 KB Output is correct
35 Correct 512 ms 41600 KB Output is correct
36 Correct 296 ms 39424 KB Output is correct
37 Correct 401 ms 41048 KB Output is correct
38 Correct 535 ms 38608 KB Output is correct
39 Correct 632 ms 39500 KB Output is correct
40 Correct 512 ms 38468 KB Output is correct
41 Correct 144 ms 36212 KB Output is correct
42 Correct 153 ms 36020 KB Output is correct
43 Incorrect 170 ms 35900 KB Output isn't correct
44 Halted 0 ms 0 KB -