oj.uz

Submission #568564

# Submission time Handle Problem Language Result Execution time Memory
568564 2022-05-25T17:08:33 Z FEDIKUS Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 38388 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[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 && false){
            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 && false){
            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 111 ms 33100 KB Output is correct
2 Correct 114 ms 33124 KB Output is correct
3 Correct 106 ms 33156 KB Output is correct
4 Correct 108 ms 33128 KB Output is correct
5 Correct 130 ms 33132 KB Output is correct
6 Correct 104 ms 33124 KB Output is correct
7 Correct 109 ms 33128 KB Output is correct
8 Correct 121 ms 33112 KB Output is correct
9 Correct 115 ms 33108 KB Output is correct
10 Correct 112 ms 33108 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33100 KB Output is correct
2 Correct 114 ms 33124 KB Output is correct
3 Correct 106 ms 33156 KB Output is correct
4 Correct 108 ms 33128 KB Output is correct
5 Correct 130 ms 33132 KB Output is correct
6 Correct 104 ms 33124 KB Output is correct
7 Correct 109 ms 33128 KB Output is correct
8 Correct 121 ms 33112 KB Output is correct
9 Correct 115 ms 33108 KB Output is correct
10 Correct 112 ms 33108 KB Output is correct
11 Correct 343 ms 37140 KB Output is correct
12 Correct 371 ms 36804 KB Output is correct
13 Correct 300 ms 36032 KB Output is correct
14 Correct 297 ms 36068 KB Output is correct
15 Correct 372 ms 37124 KB Output is correct
16 Correct 335 ms 36228 KB Output is correct
17 Correct 319 ms 36288 KB Output is correct
18 Correct 1528 ms 38260 KB Output is correct
19 Correct 260 ms 35020 KB Output is correct
20 Correct 384 ms 36788 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33100 KB Output is correct
2 Correct 114 ms 33124 KB Output is correct
3 Correct 106 ms 33156 KB Output is correct
4 Correct 108 ms 33128 KB Output is correct
5 Correct 130 ms 33132 KB Output is correct
6 Correct 104 ms 33124 KB Output is correct
7 Correct 109 ms 33128 KB Output is correct
8 Correct 121 ms 33112 KB Output is correct
9 Correct 115 ms 33108 KB Output is correct
10 Correct 112 ms 33108 KB Output is correct
11 Correct 343 ms 37140 KB Output is correct
12 Correct 371 ms 36804 KB Output is correct
13 Correct 300 ms 36032 KB Output is correct
14 Correct 297 ms 36068 KB Output is correct
15 Correct 372 ms 37124 KB Output is correct
16 Correct 335 ms 36228 KB Output is correct
17 Correct 319 ms 36288 KB Output is correct
18 Correct 1528 ms 38260 KB Output is correct
19 Correct 260 ms 35020 KB Output is correct
20 Correct 384 ms 36788 KB Output is correct
21 Correct 491 ms 37284 KB Output is correct
22 Correct 567 ms 37564 KB Output is correct
23 Correct 322 ms 36428 KB Output is correct
24 Correct 313 ms 36396 KB Output is correct
25 Correct 629 ms 38388 KB Output is correct
26 Correct 378 ms 36736 KB Output is correct
27 Correct 388 ms 36756 KB Output is correct
28 Execution timed out 2081 ms 34360 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33100 KB Output is correct
2 Correct 114 ms 33124 KB Output is correct
3 Correct 106 ms 33156 KB Output is correct
4 Correct 108 ms 33128 KB Output is correct
5 Correct 130 ms 33132 KB Output is correct
6 Correct 104 ms 33124 KB Output is correct
7 Correct 109 ms 33128 KB Output is correct
8 Correct 121 ms 33112 KB Output is correct
9 Correct 115 ms 33108 KB Output is correct
10 Correct 112 ms 33108 KB Output is correct
11 Correct 221 ms 34636 KB Output is correct
12 Correct 309 ms 34672 KB Output is correct
13 Correct 136 ms 34540 KB Output is correct
14 Correct 142 ms 36460 KB Output is correct
15 Correct 636 ms 36664 KB Output is correct
16 Correct 149 ms 36448 KB Output is correct
17 Correct 145 ms 36444 KB Output is correct
18 Execution timed out 2059 ms 35684 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 33100 KB Output is correct
2 Correct 114 ms 33124 KB Output is correct
3 Correct 106 ms 33156 KB Output is correct
4 Correct 108 ms 33128 KB Output is correct
5 Correct 130 ms 33132 KB Output is correct
6 Correct 104 ms 33124 KB Output is correct
7 Correct 109 ms 33128 KB Output is correct
8 Correct 121 ms 33112 KB Output is correct
9 Correct 115 ms 33108 KB Output is correct
10 Correct 112 ms 33108 KB Output is correct
11 Correct 343 ms 37140 KB Output is correct
12 Correct 371 ms 36804 KB Output is correct
13 Correct 300 ms 36032 KB Output is correct
14 Correct 297 ms 36068 KB Output is correct
15 Correct 372 ms 37124 KB Output is correct
16 Correct 335 ms 36228 KB Output is correct
17 Correct 319 ms 36288 KB Output is correct
18 Correct 1528 ms 38260 KB Output is correct
19 Correct 260 ms 35020 KB Output is correct
20 Correct 384 ms 36788 KB Output is correct
21 Correct 491 ms 37284 KB Output is correct
22 Correct 567 ms 37564 KB Output is correct
23 Correct 322 ms 36428 KB Output is correct
24 Correct 313 ms 36396 KB Output is correct
25 Correct 629 ms 38388 KB Output is correct
26 Correct 378 ms 36736 KB Output is correct
27 Correct 388 ms 36756 KB Output is correct
28 Execution timed out 2081 ms 34360 KB Time limit exceeded
29 Halted 0 ms 0 KB -