oj.uz

Submission #568565

# Submission time Handle Problem Language Result Execution time Memory
568565 2022-05-25T17:09:29 Z FEDIKUS Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 2000 ms 21748 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 && 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 47 ms 16724 KB Output is correct
2 Correct 46 ms 16724 KB Output is correct
3 Correct 52 ms 16728 KB Output is correct
4 Correct 65 ms 16720 KB Output is correct
5 Correct 51 ms 16724 KB Output is correct
6 Correct 52 ms 16716 KB Output is correct
7 Correct 44 ms 16716 KB Output is correct
8 Correct 49 ms 16844 KB Output is correct
9 Correct 52 ms 16592 KB Output is correct
10 Correct 54 ms 16724 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16724 KB Output is correct
2 Correct 46 ms 16724 KB Output is correct
3 Correct 52 ms 16728 KB Output is correct
4 Correct 65 ms 16720 KB Output is correct
5 Correct 51 ms 16724 KB Output is correct
6 Correct 52 ms 16716 KB Output is correct
7 Correct 44 ms 16716 KB Output is correct
8 Correct 49 ms 16844 KB Output is correct
9 Correct 52 ms 16592 KB Output is correct
10 Correct 54 ms 16724 KB Output is correct
11 Correct 285 ms 20704 KB Output is correct
12 Correct 327 ms 20312 KB Output is correct
13 Correct 217 ms 19532 KB Output is correct
14 Correct 246 ms 19660 KB Output is correct
15 Correct 297 ms 20816 KB Output is correct
16 Correct 249 ms 19860 KB Output is correct
17 Correct 249 ms 19780 KB Output is correct
18 Correct 1390 ms 21676 KB Output is correct
19 Correct 213 ms 18772 KB Output is correct
20 Correct 303 ms 20408 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16724 KB Output is correct
2 Correct 46 ms 16724 KB Output is correct
3 Correct 52 ms 16728 KB Output is correct
4 Correct 65 ms 16720 KB Output is correct
5 Correct 51 ms 16724 KB Output is correct
6 Correct 52 ms 16716 KB Output is correct
7 Correct 44 ms 16716 KB Output is correct
8 Correct 49 ms 16844 KB Output is correct
9 Correct 52 ms 16592 KB Output is correct
10 Correct 54 ms 16724 KB Output is correct
11 Correct 285 ms 20704 KB Output is correct
12 Correct 327 ms 20312 KB Output is correct
13 Correct 217 ms 19532 KB Output is correct
14 Correct 246 ms 19660 KB Output is correct
15 Correct 297 ms 20816 KB Output is correct
16 Correct 249 ms 19860 KB Output is correct
17 Correct 249 ms 19780 KB Output is correct
18 Correct 1390 ms 21676 KB Output is correct
19 Correct 213 ms 18772 KB Output is correct
20 Correct 303 ms 20408 KB Output is correct
21 Correct 472 ms 20752 KB Output is correct
22 Correct 502 ms 20924 KB Output is correct
23 Correct 267 ms 19828 KB Output is correct
24 Correct 285 ms 19680 KB Output is correct
25 Correct 555 ms 21748 KB Output is correct
26 Correct 297 ms 20148 KB Output is correct
27 Correct 292 ms 20172 KB Output is correct
28 Execution timed out 2083 ms 17936 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16724 KB Output is correct
2 Correct 46 ms 16724 KB Output is correct
3 Correct 52 ms 16728 KB Output is correct
4 Correct 65 ms 16720 KB Output is correct
5 Correct 51 ms 16724 KB Output is correct
6 Correct 52 ms 16716 KB Output is correct
7 Correct 44 ms 16716 KB Output is correct
8 Correct 49 ms 16844 KB Output is correct
9 Correct 52 ms 16592 KB Output is correct
10 Correct 54 ms 16724 KB Output is correct
11 Correct 139 ms 18140 KB Output is correct
12 Correct 268 ms 18208 KB Output is correct
13 Correct 71 ms 18016 KB Output is correct
14 Correct 75 ms 18012 KB Output is correct
15 Correct 573 ms 18176 KB Output is correct
16 Correct 85 ms 17988 KB Output is correct
17 Correct 91 ms 18012 KB Output is correct
18 Execution timed out 2068 ms 17884 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 16724 KB Output is correct
2 Correct 46 ms 16724 KB Output is correct
3 Correct 52 ms 16728 KB Output is correct
4 Correct 65 ms 16720 KB Output is correct
5 Correct 51 ms 16724 KB Output is correct
6 Correct 52 ms 16716 KB Output is correct
7 Correct 44 ms 16716 KB Output is correct
8 Correct 49 ms 16844 KB Output is correct
9 Correct 52 ms 16592 KB Output is correct
10 Correct 54 ms 16724 KB Output is correct
11 Correct 285 ms 20704 KB Output is correct
12 Correct 327 ms 20312 KB Output is correct
13 Correct 217 ms 19532 KB Output is correct
14 Correct 246 ms 19660 KB Output is correct
15 Correct 297 ms 20816 KB Output is correct
16 Correct 249 ms 19860 KB Output is correct
17 Correct 249 ms 19780 KB Output is correct
18 Correct 1390 ms 21676 KB Output is correct
19 Correct 213 ms 18772 KB Output is correct
20 Correct 303 ms 20408 KB Output is correct
21 Correct 472 ms 20752 KB Output is correct
22 Correct 502 ms 20924 KB Output is correct
23 Correct 267 ms 19828 KB Output is correct
24 Correct 285 ms 19680 KB Output is correct
25 Correct 555 ms 21748 KB Output is correct
26 Correct 297 ms 20148 KB Output is correct
27 Correct 292 ms 20172 KB Output is correct
28 Execution timed out 2083 ms 17936 KB Time limit exceeded
29 Halted 0 ms 0 KB -