oj.uz

Submission #785452

# Submission time Handle Problem Language Result Execution time Memory
785452 2023-07-17T09:14:43 Z Denkata Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
#define endl '\n'
#pragma GCC optimize("Ofast")
using namespace std;
string s,val;
int i,j,p,q,n,m,k,l,Q,A,B,C;
int dp[(1<<21)],subdp[(1<<21)];
int bitcnt[(1<<21)],ans;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>l>>Q;
    n = (1<<l);
    cin>>val;
    for(i=1; i<n; i++)
        bitcnt[i] = bitcnt[i/2]+i%2;
    for(i=0; i<n; i++)
        dp[i] = subdp[i] = val[i]-'0';
    for(i=0; i<l; i++)
    {
        for(j=0; j<n; j++)
        {
            if((j&(1<<i))==0)
                dp[j]+=dp[j^(1<<i)];
            else subdp[j]+=subdp[j^(1<<i)];
            ///1 za sub/ 0 za super
        }
    }
    while(Q--)
    {
        cin>>s;
        A = B = C = 0;
        ans = 0;
        for(i=0; i<l; i++)
        {
            if(s[i]=='0')
                A |= (1<<(l-i-1));
            else if(s[i]=='1')
                B |= (1<<(l-i-1));
            else
                C |= (1<<(l-i-1));

        }
        ///tva e mega dobro
        if(bitcnt[C]<=bitcnt[A] && bitcnt[C]<=bitcnt[B])
        {
            ///vsichki podmnojestva ot setnatite bitove na C
            for(int m=C; m!=0; m=(m-1)&C)
            {
                ans+=val[m|B]-'0';
            }
            ans+=val[B]-'0';
        }
        ///tva e mega dobro
        else if(bitcnt[A]<=bitcnt[B])
        {
            for(int m=A;m!=0;m=(m-1)&A)
            {
                if(bitcnt[m]%2==0)
                    ans+=dp[m|B];
                else
                    ans-=dp[m|B];
            }
            ans+=dp[B];
        }
        else
        {
            for(int m=B;m!=0;m=(m-1)&B)
            {
                if((bitcnt[m])%2==0)
                    ans+=subdp[m|C];
                else
                    ans-=subdp[m|C];
            }
            //ans+=subdp[C|];
            if(bitcnt[B]%2==0)ans+=subdp[C];
            else ans-=subdp[C];
        }
        cout<<ans<<endl;

    }
    return 0;
}
///precompute bit count for speed up

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -