Submission #1276549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276549		sasde	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1052 ms	17792 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define emb emplace_back
const int N=2e6+5;
int node,query,ans;
string s,x;
int dpcha[N],dpcon[N],po[N];
vector<int>res;
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
        #define task "a"
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    cin >> node >> query >> s;
    for(int i=0;i<(1<<node);++i){
        dpcon[i]=s[i]-'0';
        dpcha[i]=s[i]-'0';
    }
    for(int j=0;j<node;++j){
    for(int mask=0;mask<(1<<node);++mask){
            if(mask>>j&1)dpcha[mask]+=dpcha[mask^(1<<j)];
            else dpcon[mask]+=dpcon[mask^(1<<j)];
        }
    }
    // cout <<dp[]
    while(query--){
        cin >> x;
        vector<int>vec[3];
        ans=0;
        reverse(all(x));
        for(int i=0;i<sz(x);++i){
            char y=x[i];
            if(y=='?')vec[0].emb(i);
            if(y=='0')vec[1].emb(i);
            if(y=='1')vec[2].emb(i);
        }
        if(sz(vec[1])<=sz(x)/3){
            int mask=0;
            for(int i=0;i<node;++i)
                if(x[i]=='1')mask|=(1<<i);
            for(int i=0;i<(1<<sz(vec[1]));++i){
                int cnt=__builtin_popcount(i);
                int moc=mask;
                for(int j=0;j<sz(vec[1]);++j){
                    if((i>>j)&1)moc^=(1<<vec[1][j]);
                }
                if(cnt&1)ans-=dpcon[moc];
                else ans+=dpcon[moc];
            }
        }
        else
        if(sz(vec[2])<=sz(x)/3){
            int mask=0;
            for(int i=0;i<node;++i)
                if(x[i]=='1'||x[i]=='?')mask|=(1<<i);
            for(int i=0;i<(1<<sz(vec[2]));++i){
                int cnt=__builtin_popcount(i);
                int moc=mask;
                for(int j=0;j<sz(vec[2]);++j){
                    if((i>>j)&1)moc^=(1<<vec[2][j]);
                }
                if(cnt&1)ans-=dpcha[moc];
                else ans+=dpcha[moc];
            }
        }
        else
        {
            int mask=0;
            for(int i=0;i<node;++i)
                if(x[i]=='1')mask|=(1<<i);
            for(int i=0;i<(1<<sz(vec[0]));++i){
                int cnt=__builtin_popcount(i);
                int moc=mask;
                for(int j=0;j<sz(vec[0]);++j){
                    if((i>>j)&1)moc^=(1<<vec[0][j]);
                }
                ans+=s[moc]-'0';
            }
        }
        cout <<ans<<'\n';
    }
}

Compilation message (stderr)

snake_escaping.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main()
      | ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:18:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:19:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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