Submission #844729

#	Time	Username	Problem	Language	Result	Execution time	Memory
844729		damwuan	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1387 ms	55640 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=(1<<20)+5;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int l,q,n,dp[maxn],dp1[maxn],f[maxn],ans;
string ss,s;
vector<int> L;
void solve0()
{
    reverse(s.begin(),s.end());
    L.clear();
    int ori=0;
    for1(i,0,s.size()-1)
    {
        if (s[i]=='0') L.pb(i);
        if (s[i]=='1') ori+=(1<<i);
    }
    int g=L.size(),ori2;
    ans=0;
    for1(mask1,0,(1<<g)-1)
    {
        ori2=ori;
        for1(j,0,g-1)
        {
            if ((mask1>>j)&1) ori2+=(1<<L[j]);
        }
        if (__builtin_popcount(mask1)%2==0)
        {
            //cerr<< ori2<<'\n';
            ans+=dp1[ori2];
        }
        else ans-=dp1[ori2];
    }
    cout << ans<<'\n';
}
void solve1()
{
    reverse(s.begin(),s.end());
    L.clear();
    int ori=0;
    for1(i,0,s.size()-1)
    {
        if (s[i]=='1') L.pb(i);
        if (s[i]=='1' || s[i]=='?') ori+=(1<<i);
    }
    int g=L.size(),ori2;
    ans=0;
    for1(mask1,0,(1<<g)-1)
    {
        ori2=ori;
        for1(j,0,g-1)
        {
            if ((mask1>>j)&1) ori2^=(1<<L[j]);
        }
        if (__builtin_popcount(mask1)%2==0)
        {
            //cerr<< ori2<<'\n';
            ans+=dp[ori2];
        }
        else ans-=dp[ori2];
    }
    cout << ans<<'\n';
}
void solve()
{

    reverse(s.begin(),s.end());
    L.clear();
    int ori=0;
    for1(i,0,s.size()-1)
    {
        if (s[i]=='?') L.pb(i);
        if (s[i]=='1') ori+=(1<<i);
    }
    int g=L.size(),ori2;
    ans=0;
    for1(mask1,0,(1<<g)-1)
    {
        ori2=ori;
        for1(j,0,g-1)
        {
            if ((mask1>>j)&1) ori2+=(1<<L[j]);
        }
        ans+=f[ori2];
    }
    cout << ans<<'\n';
}

void sol()
{
    cin >> l>> q>>ss;
    n=1LL<<l;
    for1(i,0,n-1)
    {
        f[i]=dp[i]=dp1[i]=(ss[i]-'0');
    }
    for1(i,0,l-1)
    {
        for1(mask,0,n-1)
        {
            if ((mask>>i)&1)
            {
                dp[mask]+=dp[mask^(1<<i)];
            }
            else
            {
                dp1[mask]+=dp1[mask^(1<<i)];
            }
        }
    }
    /*
    dp la tong mask con
    dp1 la tong mask cha
    */
//    cout << dp1[3];
    while (q--)
    {
        cin >> s;
        int cnt1=0,cnt0=0;
        for1(i,0,s.size()-1)
        {
            if (s[i]=='0') cnt0++;
            if (s[i]=='1') cnt1++;
        }
        if (cnt1<7)
        {
            solve1();
        }
        else if (cnt0<7)
        {
            solve0();
        }
        else
        {
            solve();
        }
    }


}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("GROUPDIV.inp","r",stdin);
//    freopen("GROUPDIV.out","w",stdout);

    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}
/*

3 1
12345678
?11
*/

Compilation message (stderr)

snake_escaping.cpp: In function 'void solve0()':
snake_escaping.cpp:11:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
   37 |     for1(i,0,s.size()-1)
      |          ~~~~~~~~~~~~~~           
snake_escaping.cpp:37:5: note: in expansion of macro 'for1'
   37 |     for1(i,0,s.size()-1)
      |     ^~~~
snake_escaping.cpp: In function 'void solve1()':
snake_escaping.cpp:11:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
   65 |     for1(i,0,s.size()-1)
      |          ~~~~~~~~~~~~~~           
snake_escaping.cpp:65:5: note: in expansion of macro 'for1'
   65 |     for1(i,0,s.size()-1)
      |     ^~~~
snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:11:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
   94 |     for1(i,0,s.size()-1)
      |          ~~~~~~~~~~~~~~           
snake_escaping.cpp:94:5: note: in expansion of macro 'for1'
   94 |     for1(i,0,s.size()-1)
      |     ^~~~
snake_escaping.cpp: In function 'void sol()':
snake_escaping.cpp:11:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define for1(i,j,k) for(int i=j;i<=k;i++)
......
  144 |         for1(i,0,s.size()-1)
      |              ~~~~~~~~~~~~~~       
snake_escaping.cpp:144:9: note: in expansion of macro 'for1'
  144 |         for1(i,0,s.size()-1)
      |         ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25